Курсовая работа: Генетические алгоритмы в задаче оптимизации действительных параметров
Таблица 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();
}
Заключение
Изложенный подход является эвристическим, т. е. показывает хорошие результаты на практике, но плохо поддается теоретическому исследованию и обоснованию. Естественно задать вопрос — следует ли пользоваться такими алгоритмами, не имеющими строгого математического обоснования? Как и в вопросе о нейронных сетях, здесь нельзя ответить однозначно. С одной стороны, в математике существует достаточно большой класс абсолютно надежных (в смысле гарантии получения точного решения) методов решения различных задач. С другой стороны, речь идет о действительно сложных практических задачах, в которых эти надежные методы часто неприменимы. Нередко эти задачи выглядят настолько необозримыми, что не предпринимается даже попыток их осмысленного решения. Например, фирма, занимающаяся транспортными перевозками, в современных условиях российского бизнеса скорее предпочтет нанять лишних водителей и повысить цены на свои услуги, чем оптимизировать маршруты и расписания поездок. На западном рынке, где уже давно действуют законы более или менее честной конкуренции, оптимальность деятельности компании значительно влияет на ее доходы и даже может стать решающим фактором для ее выживания. Поэтому любые идеи, позволяющие компании стать «умнее» своих конкурентов, находят там широкое применение. Генетические алгоритмы — реализация одной из наиболее популярных идей такого рода. Эта популярность вызвана, по-видимому, исключительной красотой подхода и его близостью к природному механизму. Подобным образом популярность нейросетевой технологии подогревается во многом ее сходством с работой мозга. По-настоящему активное развитие эвристических подходов, как мы видим, непосредственно связано с развитием свободного рынка и экономики в целом.
Список использованной литературы
1. Кантор И.А.(перевод) Введение в ГА и Генетическое Программирование -http://www. algolist.manual.ru
2. Скурихин А.Н. Генетические алгоритмы . Новости искусственного интеллекта - 1995, №4, с. 6-46.
3. Хэзфилд Р. , Кирби Л. Искусство программирования на C – К .:DIAsoft ,2001.
4. Поспелов Д.А. Информатика. Энциклопедический словарь для начинающих - М:Педагогика-Пресс, 1994, - 350 с.
5. Курс лекций по предмету "Основы проектирования систем с искусственным интеллектом" / Сост. Сотник С.Л. –URL:http://www.neuropower.de
6. Кузнецов О.П. О некомпьютерных подходах к моделированию интеллектуальных процессов мозга – Москва, Институт проблем управления РАН
7. Самоорганизующиеся нейронные сети и их применение – URL:http://www.chat.ru/~neurolab
8. Редько В.Г. Курс лекций "Эволюционная кибернетика" – URL:http://inet.keldysh.ru/BioCyber/Lectures.html
9. Головко В.А. Нейроинтеллект: Теория и применения Книга 1 Организация и обучение нейронных сетей с прямыми и обратными связями - Брест:БПИ, 1999, - 260 с.
10. Головко В.А. Нейроинтеллект: Теория и применения Книга 2 Самоорганизация, отказоустойчивость и применение нейронных сетей - Брест:БПИ, 1999, - 228 с.
11. А.Н. Генетические алгоритмы . Новости искусственного интеллекта - 1995, №4, с. 6-46.
12. С.А. Исаев Генетические алгоритмы - эволюционные методы поиска -URL: http://rv.ryazan.ru/~bug/library/ai/isaev/2/part1.html
13. Д.И. Батищев, С.А. Исаев Оптимизация многоэкстремальных функций с помощью генетических алгоритмов -URL:http://bspu.secna.ru/Docs/~saisa/ga/summer97.html
14. Group Method of Data Handling - URL: http://www.inf.kiev.ua/GMDH-home
15. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации.- Новосибирск: Наука, 1978.
16. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982.
17. Лима-ле-Фариа А. Эволюция без отбора: Автоэволюция формы и функции.- Москва, "Мир", 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)
{ // Считаем до тех пор пока решение
// не будет найдено или к-во итераций более 50
GenerateLikelihoods();
CreateNewPopulation();
if (fitness = CreateFitnesses())
{
printf("iterations %d \n",iterations);
return fitness;
}
iterations++;
}
return -1;
}
int 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 ,если среди генов данной
// популяции не нашлось решения
}
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);
}
}
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;
}
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];
}
