Генетические алгоритмы (стр. 3 из 5)

Вывод

Итак, изложенный подход к изучению генетических алгоритмов является эвристическим, т. е. показывает хорошие результаты на практике, но плохо поддается теоретическому исследованию и обоснованию. Естественно задать вопрос — следует ли пользоваться такими алгоритмами, не имеющими строгого математического обоснования?

Как и в вопросе о нейронных сетях, здесь нельзя ответить однозначно. С одной стороны, в математике существует достаточно большой класс абсолютно надежных (в смысле гарантии получения точного решения) методов решения различных задач. С другой стороны, речь идет о действительно сложных практических задачах, в которых эти надежные методы часто неприменимы. Нередко эти задачи выглядят настолько необозримыми, что не предпринимается даже попыток их осмысленного решения.[15]

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

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

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

ГЛАВА 2. ЗАДАЧИ ОПТИМИЗАЦИИ.

2.1 Задачи, решаемые с помощью генетических алгоритмов

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

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

2.2 Математическая постановка задачи оптимизации

Постановка задачи оптимизации включает в себя множество допустимых решений

и числовую функцию , определенную на этом множестве, которая называется целевой функцией.

Нельзя отождествлять критерий (критерии) оптимальности и целевую функцию.

Целевая функция – это аналитическая зависимость между критерием (критериями) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума.

Отличие понятий «критерий» и «целевая функция» состоит в следующем:

1. Целевая функция может включать в себя более одного критерия.

2. Для целевой функции всегда и обязательно указывается вид экстремума:

Различают два вида задач оптимизации:

oЗадачу минимизации.

oЗадачу максимизации.

Чтобы решить задачу минимизации функции

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

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

В общем виде находится именно вектор

, т.к., например, при решении двухпараметрической задачи, он будет включать в себя два параметра, трехпараметрической – три параметра и т.д.

2.3 Решение Диофантова уравнения

Рассмотрим Диофантово (только целые решения) уравнение: 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.

Хромосома	(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)

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

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

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

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

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

Хромосома	Подходимость
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%

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

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

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

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

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

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

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

А теперь попробуем проделать это с нашими потомками

Хромосома-отец	Хромосома-мать	Хромосома-потомок
(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)

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