Xreferat.com » Рефераты по биологии » Генетические алгоритмы в задаче оптимизации действительных параметров

Генетические алгоритмы в задаче оптимизации действительных параметров

иного оператора. Более того, было показано, что использование механизма случайного выбора одно- или двух точечного кроссовера для каждой конкретной брачной пары подчас оказывается более эффективным, чем детерминированный подход к выбору кроссоверов, поскольку достаточно трудно определить который из двух операторов более подходит для каждого конкретного ландшафта приспособленности. Использование же случайного выбора преследовало целью, прежде всего сгладить различия этих двух подходов и улучшить показатели среднего ожидаемого результата. Для всех представленных тестовых функций так и произошло, - случайного выбор оказался эффективнее худшего.

Повышение эффективности поиска при использовании случайного выбора операторов кроссовера повлияло на то, чтобы применить аналогичный подход при реализации процесса мутагенеза новых особей, однако в этом случае преимущество перед детерминированным подходом не так очевидно в силу традиционно малой вероятности мутации. В основном вероятность мутации составляет 0.001 - 0.01.


3.2 Выбор родительской пары


Первый подход самый простой - это случайный выбор родительской пары ("панмиксия"), когда обе особи, которые составят родительскую пару, случайным образом выбираются из

всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции. Второй способ выбора особей в родительскую пару - так называемый селективный. Его суть состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставиться задача определения нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений. Кроме того, для некоторого класса задач со сложным ландшафтом приспособленности быстрая сходимость может превратиться в преждевременную сходимость к квазиоптимальному решению. Этот недостаток может быть отчасти компенсирован использованием подходящего механизма отбора, который бы "тормозил" слишком быструю сходимость алгоритма. Другие два способа формирования родительской пары, на которые хотелось бы обратить внимание, это инбридинг и аутбридинг. Оба эти метода построены на формировании пары на основе близкого и дальнего "родства" соответственно. Под "родством" здесь понимается расстояние между членами популяции как в смысле геометрического расстояния особей в пространстве параметров. В связи с этим будем различать генотипный и фенотипный (или географический) инбридинг и аутбридинг. Под инбридингом понимается такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь. Аутбридинг же, наоборот, формирует брачные пары из максимально далеких особей. Использование генетических инбридинга и аутбридинга оказалось более эффективным по сравнению с географическим для всех тестовых функций при различных параметрах алгоритма. Наиболее полезно применение обоих представленных методов для многоэкстремальных задач. Однако два этих способа по-разному влияют на поведение генетического алгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта, напротив аутбридинг как раз направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.


3.3 Механизм отбора


Обсуждение вопроса о влиянии метода создания родительских пар на поведение генетического алгоритма невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Наиболее эффективные два механизма отбора элитный и отбор с вытеснением.

Идея элитного отбора, в общем, не нова, этот метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Именно такая комбинация "аутбридинг - элитный отбор" является одной из наиболее эффективных.

Второй метод, на котором хотелось бы остановиться, это отбор вытеснением. Будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из далеко расположенных особей, вместо особей, группирующихся около текущего найденного решения. Этот метод особенно хорошо себя показал при решении многоэкстремальных задач, при этом помимо определения глобальных экстремумов появляется возможность выделить и те локальные максимумы, значения которых близки к глобальным.


4. Наиболее актуальные проблемы ГА и интересные модификации ГА


Неудачный выбор упорядочивания и кодирования битов в хромосоме может вызвать преждевременное схождение к локальному оптимуму, ведя алгоритм по ложному пути. Для преодоления этого недостатка можно выбирать способ кодирования основываясь на дополнительной информации о задаче. Существуют так же мобильные ГА, с переменной длиной хромосом. Для некоторых задач такое представление естественно, для других надо вводить специальные правила чтения хромосом. Вместо оператора кроссинговера используются операторы разрезания строк (CUT), вероятность которого повышается с увеличением длины строки, и оператор сцепления строк (SPLICE), который выбирает из популяции два куска и сцепляет их в один кусок. Популяция представляет собой совокупность пере- и недоопределённых строк. Правила чтения таких строк могут быть, например такими: в переопределённой строке при чтении слева направо не учитываются уже использованные гены, а в недоопределённых строках отсутствующие места заимствуются у лучшего элемента.

Проблема баланса исследования новых областей и приспособления к найденным. Это необходимо для предотвращения преждевременной сходимости к локальному оптимуму. Используются модифицированные способы отбора хромосом в промежуточную популяцию (отказ от вероятностных принципов в пользу элитного и отбора с вытеснением) и выбора родительской пары (случайный, селективный, на основе близкого или дальнего родства).

Интересные результаты может дать сочетание ГА с другими методами. И в заключение остановимся на том, когда же следует использовать генетические алгоритмы. В одних обстоятельствах они хороши, в других - не очень. В общем случае генетические алгоритмы не находят оптимального решения очень трудных задач. Если оптимальное решение задачи (например, ЗКВ с очень большим числом городов) не может быть найдено традиционными способами - например, методом сцепления ветвей (branch and bound method), - то и генетический алгоритм вряд ли найдет оптимум. С другой стороны, вполне возможно, что генетический алгоритм найдет достаточно хорошее решение. В конце концов, коммивояжеру в любом случае надо ехать продавать свои товары, даже если мы не уверены в абсолютной оптимальности маршрута! Но есть примеры, когда в очень трудных задачах, в том числе и в ЗКВ, с помощью генетических алгоритмов были получены очень хорошие решения.

В двух случаях генетические алгоритмы очень хороши. Первый случай: когда не известен способ точного решения задачи. Если мы знаем, как оценить приспособленность хромосом, то всегда можем заставить генетический алгоритм решать эту задачу. Второй случай: когда способ для точного решения существует, но он очень сложен в реализации, требует больших затрат времени и денег, то есть, попросту говоря, дело того не стоит. Пример - создание программы для составления персонального расписания на основе техники покрытия множеств с использованием линейного программирования.

Несмотря на то, что конструирование хромосом и фитнес-функций может потребовать значительных усилий, генетические алгоритмы легко реализуются даже с нуля и способны решать широкий круг задач. Используя аналогию с развитием живых организмов от простых форм к более сложным, генетические алгоритмы приблизились к тому, чтобы стать общим методом решения задач. Другие "природоподобные" парадигмы, такие как моделирование отжига (simulated annealing) и табу-поиск (taboo search), тоже позволяют решать аналогичные задачи.


5. Пример ГА: Решение Диофантова уравнения


Рассмотрим диофантово (только целые решения) уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d). Конечно, Вы можете спросить: почему бы не использовать метод грубой силы: просто не подставить все возможные значения a, b, c, d (очевидно, 1 <= a,b,c,d <= 30) ? Архитектура ГА-систем позволяет найти решение быстрее за счет более 'осмысленного' перебора. Мы не перебираем все подряд, но приближаемся от случайно выбранных решений к лучшим. Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Вообще говоря, мы можем использовать меньшее ограничение для b,c,d, но для упрощения пусть будет 30.


Таблица 2: 1-е поколение хромосом и их содержимое

Хромосома (a,b,c,d)
1 (1,28,15,3)
2 (14,9,2,4)
3 (13,5,7,3)
4 (23,8,16,19)
5 (9,13,5,2)

Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением.


Таблица 3: Коэффициенты выживаемости первого поколения хромосом (набора решений)

Хромосома Коэффициент выживаемости
1 |114-30|=84
2 |54-30|=24
3 |56-30|=26
4 |163-30|=133
5 |58-30|=28

Так как меньшие значения ближе к 30, то они более желательны. В нашем случае большие численные значения коэффициентов выживаемости подходят, увы, меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) может быть выбрана каждая. Одно решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (Заметим, что все решения были сгенерированы Генератором Случайных Чисел - ГСЧ).


Таблица 4: Вероятность оказаться родителем

Хромосома Подходящесть
1 (1/84)/0.135266 = 8.80%
2 (1/24)/0.135266 = 30.8%
3 (1/26)/0.135266 = 28.4%
4 (1/133)/0.135266 = 5.56%
5 (1/28)/0.135266 = 26.4%

Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-сторонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы.

Таблица 5: Симуляция выбора родителей

Хромосома отца Хромосома матери
3 1
5 2
3 5
2 5
5 3

Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кросс-оверов (| = разделительная линия):


Таблица 6: Кроссоверы между родителями

Хромосома-отец Хромосома-мать Хромосома-потомок
a1 | b1,c1,d1 a2 | b2,c2,d2 a1,b2,c2,d2 or a2,b1,c1,d1
a1,b1 | c1,d1 a2,b2 | c2,d2 a1,b1,c2,d2 or a2,b2,c1,d1
a1,b1,c1 | d1 a2,b2,c2 | d2 a1,b1,c1,d2 or a2,b2,c2,d1

Есть достаточно много путей передачи информации потомку, и кроссовер - только один из них. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты. А теперь попробуем проделать это с нашими потомками


Таблица 7: Симуляция кроссоверов хромосом родителей

Хромосома-отец Хромосома-мать Хромосома-потомок
(13 | 5,7,3) (1 | 28,15,3) (13,28,15,3)
(9,13 | 5,2) (14,9 | 2,4) (9,13,2,4)
(13,5,7 | 3) (9,13,5 | 2) (13,5,7,2)
(14 | 9,2,4) (9 | 13,5,2) (14,13,5,2)
(13,5 | 7, 3) (9,13 | 5, 2) (13,5,5,2)

Теперь мы можем вычислить коэффициенты выживаемости (fitness) потомков.


Таблица 8: Коэффициенты выживаемости потомков (fitness)

Хромосома-потомок Коэффициент выживаемости
(13,28,15,3) |126-30|=96
(9,13,2,4) |57-30|=27
(13,5,7,2) |57-30|=22
(14,13,5,2) |63-30|=33
(13,5,5,2) |46-30|=16

Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4. Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30. Продолжая таким образом, одна хромосома, в конце концов, достигнет коэффициента выживаемости 0, то есть станет решением. Системы с большей популяцией (например, 50 вместо 5-и сходятся к желаемому уровню (0) более быстро и стабильно.


5.1 Заголовок класса


#include <stdlib.h>

#include <time.h>

#include<stdio.h>

#define MAXPOP 25

struct gene

{

int alleles[4];

int fitness;

float likelihood; // Тест на равенство

operator==(gene gn)

for (int i=0;i<4;i++)

{

if (gn.alleles[i] != alleles[i]) return false;

}

return true;

class CDiophantine

public:

CDiophantine(int, int, int, int, int); // Конструктор с коэффициентами при а,b,c,d

int Solve(); // Вычисляет решение уравнения


gene GetGene(int i)

{ return population[i];}

protected:

int ca,cb,cc,cd; // Коэффициенты при а,b,c,d

int result;

gene population[MAXPOP]; // Массив из генов - популяция

int Fitness(gene &); // Функция приспособленности

void GenerateLikelihoods(); // Вычисляет вероятности воспроизведения

float MultInv();


int CreateFitnesses();

void CreateNewPopulation();

int GetIndex(float val);


gene Breed(int p1, int p2);

Существуют две структуры: gene и класс CDiophantine. gene используется для слежения за различными наборами решений. Создаваемая популяция - популяция ген. Эта генетическая структура отслеживает свои коэффициенты выживаемости и вероятность оказаться родителем. Также есть небольшая функция проверки на равенство, просто чтобы сделать кое-какой другой код покороче. Теперь по функциям:


5.2 Функция Fitness


Вычисляет коэффициент выживаемости (приспособленности - fitness) каждого гена. В нашем случае это - модуль разности между желаемым результатом и полученным значением. Этот класс использует две функции: первая вычисляет все коэффициенты, а вторая - поменьше (желательно сделать ее inline) вычисляет коэффициент для какого-то одного гена.

CDiophantine::Fitness(gene &gn) //Вычисляет коэффициет приспособленности для данного гена

{

int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2] + cd * gn.alleles[3];

return gn.fitness = abs(total - result);

}

int CDiophantine::CreateFitnesses() // Возвращает номер гена в популяции ,

{ // кот. явл. решением данного ур-я

float avgfit = 0;

int fitness = 0;

for(int i=0;i<MAXPOP;i++)

{

fitness = Fitness(population[i]);

// avgfit += fitness;

if (fitness == 0)

{

return i;

}

}


return 0; //Возвращает 0 ,если среди генов данной популяции не нашлось решения

}

Заметим, что если fitness = 0, то найдено решение - возврат. После вычисления приспособленности (fitness) нам нужно вычислить вероятность выбора этого гена в качестве родительского.


5.3 Функция Likelihood


Как и было объяснено, вероятность вычисляется как сумма обращенных коэффициентов, деленная на величину, обратную к коэффициенту данному значению. Вероятности кумулятивны (складываются), что делает очень легким вычисления с родителями. Например:


Таблица

Хромосома Вероятность
1 (1/84)/0.135266 = 8.80%
2 (1/24)/0.135266 = 30.8%
3 (1/26)/0.135266 = 28.4%
4 (1/133)/0.135266 = 5.56%
5 (1/28)/0.135266 = 26.4%

В программе, при одинаковых начальных значениях, вероятности сложатся: представьте их в виде кусков пирога. Первый ген - от 0 до 8.80%, следующий идет до 39.6% (так как он начинает 8.8). Таблица вероятностей будет выглядеть приблизительно так:


Таблица

Хромосома Вероятность (smi = 0.135266)
1 (1/84)/smi = 8.80%
2 (1/24)/smi = 39.6% (30.8+8.8)
3 (1/26)/smi = 68% (28.4+39.6)
4 (1/133)/smi = 73.56% (5.56+68)
5 (1/28)/smi = 99.96% (26.4+73.56)

Последнее значение всегда будет 100. Имея в нашем арсенале теорию, посмотрим на код. Он очень прост: преобразование к float необходимо для того, чтобы избежать целочисленного деления. Есть две функции: одна вычисляет smi, а другая генерирует вероятности оказаться родителем.

float CDiophantine::MultInv()

{

float sum = 0;

for(int i=0;i<MAXPOP;i++)

{

sum += 1/((float)population[i].fitness);

}

return sum; //Сумма обратных коэффициентов приспособленности всех генов в популяции

}

void CDiophantine::GenerateLikelihoods() //Генерирует вероятности воспроизведения

{

float multinv = MultInv();

float last = 0;

for(int i=0;i<MAXPOP;i++)

{

population[i].likelihood = last = last + ((1/((float)population[i].fitness) / multinv) * 100);

}

}

Итак, у нас есть и коэффициенты выживаемости (fitness) и необходимые вероятности (likelihood). Можно переходить к размножению (breeding).


5.4 Функции Breeding


Функции размножения состоят из трех: получить индекс гена, отвечающего случайному числу от 1 до 100, непосредственно вычислить кроссовер двух генов и главной функции генерации нового поколения. Рассмотрим все эти функции одновременно и то, как они друг друга вызывают. Вот главная функция размножения:

CDiophantine::CreateNewPopulation() {

gene temppop[MAXPOP];

for(int i=0;i<MAXPOP;i++)

{

int parent1 = 0,parent2 = 0, iterations = 0;

while(parent1 == parent2 || population[parent1] == population[parent2])

{

parent1 = GetIndex((float)(rand() % 101));

parent2 = GetIndex((float)(rand() % 101));

if (++iterations > MAXPOP) break; // В этом случае родителей выбираем случайно

}


temppop[i] = Breed(parent1, parent2); // Процесс размножения

}

for(i=0;i<MAXPOP;i++)

population[i] = temppop[i];

}

Итак, первым делом мы создаем случайную популяцию генов. Затем делаем цикл по всем генам. Выбирая гены, мы не хотим, чтобы они оказались одинаковы (ни к чему скрещиваться с самим собой :), и вообще - нам не нужны одинаковые гены (operator = в gene). При выборе родителя, генерируем случайное число, а затем вызываем GetIndex. GetIndex использует идею куммулятивности вероятностей (likelihoods), она просто делает итерации по всем генам, пока не найден ген, содержащий число:

int CDiophantine::GetIndex(float val) // По данному числу от 0 до //100 возвращает

{ // номер необходимого гена в популяции

float last = 0;

for(int i=0;i<MAXPOP;i++)

{

if (last <= val && val <= population[i].likelihood) return i;

else last = population[i].likelihood;

}


return 4;

}

Возвращаясь к функции CreateNewPopulation(): если число итераций превосходит MAXPOP, она выберет любых родителей. После того, как родители выбраны, они скрещиваются: их индексы передаются вверх на функцию размножения (Breed). Breed function возвращает ген, который помещается во временную популяцию. Вот код:

gene CDiophantine::Breed(int p1, int p2)

{

int crossover = rand() % 3+1; //Число от 1 до 3 - генерируем точку кроссовера.

int first = rand() % 100; // Какой родитель будет первым ?

gene child = population[p1]; // Инициализировать ребенка первым родителем

int initial = 0, final = 4;

if (first < 50) initial = crossover;

// Если первый родитель р1(вероятность этого 50%) -

// начинаем с точки кроссовера

else final = crossover; // Иначе - заканчиваем на точке кроссовера

for(int i=initial;i<final;i++)

{ // Кроссовер

child.alleles[i] = population[p2].alleles[i];

if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1);

// 5% - мутация

}

return child; // Возвращаем ребенка

}

void CDiophantine::CreateNewPopulation() {

gene temppop[MAXPOP];

for(int i=0;i<MAXPOP;i++)

{

int parent1 = 0,parent2 = 0, iterations = 0;

while(parent1 == parent2 || population[parent1] == population[parent2])

{

parent1 = GetIndex((float)(rand() % 101));

parent2 = GetIndex((float)(rand() % 101));

if (++iterations > MAXPOP) break; // В этом случае родителей выбираем случайно

}


temppop[i] = Breed(parent1, parent2); // Процесс размножения

}

for(i=0;i<MAXPOP;i++)

population[i] = temppop[i];

}

В конце концов мы определим точку кросс-овера. Заметим, что мы нехотим, чтобы кросс-овер состоял из копирования только одного родителя. Сгенерируем случайное число, которое определит наш кроссовер. Остальное понятно и очевидно. Добавлена маленькая мутация, влияющая на скрещивание. 5% - вероятность появления нового числа.


5.5 Функция Solve


Теперь уже можно взглянуть на функцию Solve(). Она всего лишь итеративно вызывает вышеописанные функции. Заметим, что мы присутствует проверка: удалось ли функции получить результат, используя начальную популяцию. Это маловероятно, однако лучше проверить.

int CDiophantine::Solve()

{

int fitness = -1;

// Создаем начальную популяцию

srand((unsigned)time(NULL));

for(int i=0;i<MAXPOP;i++)

{ // Аллели хромосом заполняем произвольными числами от 0 до result

for (int j=0;j<4;j++)

{

population[i].alleles[j] = rand() % (result + 1);

}

}

if (fitness = CreateFitnesses())

{

return fitness;

}

int iterations = 0;

while (fitness != 0 || iterations < 50)

{ // Считаем до тех пор пока решение не будет найдено или к-во итераций более 50

GenerateLikelihoods();

CreateNewPopulation();

if (fitness = CreateFitnesses())

{

printf("iterations %d n",iterations);

return fitness;

}


iterations++;

}

return -1;

}

5.6 Функция Main


Рассмотрим код главной функции:

#include <iostream.h>

#include <conio.h>

#include "diophantine.h"

void main() {

CDiophantine dp(1,2,3,4,30);

int ans;

ans = dp.Solve();

if (ans == -1) {

cout << "Solution not found." << endl;

} else {

gene gn = dp.GetGene(ans);

cout << "The solution set to a+2b+3c+4d=30 is:n";

cout << "a = " << gn.alleles[0] << "." << endl;

cout << "b = " << gn.alleles[1] << "." << endl;

cout << "c = " << gn.alleles[2] << "." << endl;

cout << "d = " << gn.alleles[3] << "." << endl;

} getch();

}


Заключение


Изложенный подход является эвристическим, т. е. показывает хорошие результаты на практике, но плохо поддается теоретическому исследованию и обоснованию. Естественно задать вопрос — следует ли пользоваться такими алгоритмами, не имеющими строгого математического обоснования? Как и в вопросе о нейронных сетях, здесь нельзя ответить однозначно. С одной стороны, в математике существует достаточно большой класс абсолютно надежных (в смысле гарантии получения точного решения) методов решения различных задач. С другой стороны, речь идет о действительно сложных практических задачах, в которых эти надежные методы часто неприменимы. Нередко эти задачи выглядят настолько необозримыми, что не предпринимается даже попыток их осмысленного решения. Например, фирма, занимающаяся транспортными перевозками, в современных условиях российского бизнеса скорее предпочтет нанять лишних водителей и повысить цены на свои услуги, чем оптимизировать маршруты и расписания поездок. На западном рынке, где уже давно действуют законы более или менее честной конкуренции, оптимальность деятельности компании значительно влияет на ее доходы и даже может стать решающим фактором для ее выживания. Поэтому любые идеи, позволяющие компании стать «умнее» своих конкурентов, находят там широкое применение. Генетические алгоритмы — реализация одной из наиболее популярных идей такого рода. Эта популярность вызвана, по-видимому, исключительной красотой подхода и его близостью к природному механизму. Подобным образом популярность нейросетевой технологии подогревается во многом ее сходством с работой мозга. По-настоящему активное развитие эвристических подходов, как мы видим, непосредственно связано с развитием свободного рынка и экономики в целом.


Список использованной литературы


Кантор И.А.(перевод) Введение в ГА и Генетическое Программирование - algolist.manual

Скурихин А.Н. Генетические алгоритмы . Новости искусственного интеллекта - 1995, №4, с. 6-46.

Хэзфилд Р. , Кирби Л. Искусство программирования на C – К .:DIAsoft ,2001.

Поспелов Д.А. Информатика. Энциклопедический словарь для начинающих - М:Педагогика-Пресс, 1994, - 350 с.

Курс лекций по предмету "Основы проектирования систем с искусственным интеллектом" / Сост. Сотник С.Л. –URL:neuropower.de

Кузнецов О.П. О некомпьютерных подходах к моделированию интеллектуальных процессов мозга – Москва, Институт проблем управления РАН

Самоорганизующиеся нейронные сети и их применение – URL:chat/~neurolab

Редько В.Г. Курс лекций "Эволюционная кибернетика" – URL:inet.keldysh/BioCyber/Lectures.html

Головко В.А. Нейроинтеллект: Теория и применения Книга 1 Организация и обучение нейронных сетей с прямыми и обратными связями - Брест:БПИ, 1999, - 260 с.

Головко В.А. Нейроинтеллект: Теория и применения Книга 2 Самоорганизация, отказоустойчивость и применение нейронных сетей - Брест:БПИ, 1999, - 228 с.

А.Н. Генетические алгоритмы . Новости искусственного интеллекта - 1995, №4, с. 6-46.

С.А. Исаев Генетические алгоритмы - эволюционные методы поиска -URL: rv.ryazan/~bug/library/ai/isaev/2/part1.html

Д.И. Батищев, С.А. Исаев Оптимизация многоэкстремальных функций с помощью генетических алгоритмов -URL:bspu.secna/Docs/~saisa/ga/summer97.html

Group Method of Data Handling - URL: inf.kiev/GMDH-home

Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации.- Новосибирск: Наука, 1978.

Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982.

Лима-ле-Фариа А. Эволюция без отбора: Автоэволюция формы и функции.- Москва, "Мир", 1991.


Приложение А


Текст main.cpp

#include <iostream.h>

#include <conio.h>

#include "diophantine.h"

#define MAXPOP 25

void main() {

CDiophantine dp(1,2,3,4,30);

int ans;

ans = dp.Solve();

if (ans == -1) {

cout << "Solution not found." << endl;

} else {

gene gn = dp.GetGene(ans);

cout << "The solution set to a+2b+3c+4d=30 is:n";

cout << "a = " << gn.alleles[0] << "." << endl;

cout << "b = " << gn.alleles[1] << "." << endl;

cout << "c = " << gn.alleles[2] << "." << endl;

cout << "d = " << gn.alleles[3] << "." << endl;

} getch();

}


Приложение Б


Текст Diophantine.h

#include <stdlib.h>

#include <time.h>

#include<stdio.h>

//#define MAXPOP 25

struct gene

{

int alleles[4];

int fitness;

float likelihood;

// Тест на равенство

operator==(gene gn)

{

for (int i=0;i<4;i++)

{

if (gn.alleles[i] != alleles[i]) return false;

}

return true;

}

};

class CDiophantine

{

public:

CDiophantine(int, int, int, int, int); // Конструктор с коэффициентами при а,b,c,d

int Solve(); // Вычисляет решение уравнения

gene GetGene(int i)

{ return population[i];}

protected:

int ca,cb,cc,cd; // Коэффициенты при а,b,c,d

int result;

gene population[MAXPOP]; // Массив из генов - популяция

int Fitness(gene &); // Функция приспособленности

void GenerateLikelihoods(); // Вычисляет вероятности воспроизведения

float MultInv();

int CreateFitnesses();

void CreateNewPopulation();

int GetIndex(float val);

gene Breed(int p1, int p2);

};

CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {}

int CDiophantine::Solve()

{

int fitness = -1;

// Создаем начальную популяцию

srand((unsigned)time(NULL));

for(int i=0;i<MAXPOP;i++)

{ // Аллели хромосом заполняем

// произвольными числами от 0 до result

for (int j=0;j<4;j++)

{

population[i].alleles[j] = rand() % (result + 1);

}

}

if (fitness = CreateFitnesses())

{

return fitness;

}

int iterations = 0;

while (fitness != 0 || iterations < 50)

{

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: