Обобщение идей эволюционных вычислений

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

 

Основные принципы биологических систем	Основные принципы эволюционных вычислений
Наследственность, устойчивость видов. Носителями признака являются хромосомы, разделённые на гены, кодирующие различные свойства организма.	Каждое техническое решение представляет­ся набором параметров – генов, которые в совокупности составляют структурирован­ную строку, называемую по аналогии хромосомой. При алгоритмах эволюционного перебора но­вые решения, т.е. хромосомы формиру­ют­ся как комбинации из фрагментов уже существующих строк, т.е. фрагменты наследуются. Операция комбинирования фрагментов называется кроссовером.
Изменчивость. Биологические системы по мере развития приобретают новые свойства. Мутация – явление изменения содержания генов под влиянием внешних факторов.	Мутация реализуется случайным изменени­ем элемента структурированной строки хромосомы.
Принцип естественного отбора. Самый адаптируемый организм оставляет в среднем самое многочисленное потомство, поэтому полезные признаки начинают доминировать.	Для организации формирования следующего поколения в эволюционных вычислениях используют принцип пропорционального отбора или пропорциональной селекции. Ps(i) = фитнесс/ ср.фитнес поп популяции Ps – вероятность отбора f – fines-функция i – номер хромосомы.

 

 

Понятие генетического алгоритма.

3 основные положения в теории эволюции (Теория «Происхождения Видов» 1859г. Дарвина):

1. Наследственность

2. Изменчивость

3. Естественный отбор

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

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

ГА – адаптивный метод поиска, применяемый для решения задач функциональной оптимизации. Каждая хромосома оценивается мерой её «приспособленности» функцией оптимальности (fitness function) – в методах оптимизации – целевая функция. Наиболее приспособленные особи получают возможность воспроизвести потомство с помощью «перекрёстного скрещивания». Наименее приспособленные особи постепенно исчезают из популяции в процессе эволюции.

Общая схема генетического алгоритма.

1. Сгенерировать начальную популяцию

2. Пока не достигнуто значение, большее Fitness_max:

· Выбрать часть существующей популяции (отдавая предпочтение более приспособленным особям)

· Применить к этой части генетические операции, породив потомство.

· Посчитать Fitness для особей новой популяции.

Точка останова – количество поколений, заранее задаётся.

3. Установить счетчик поколений N=0, Установить максимальное число поколений N_max=max, max – любое подходящее число.

4. Вычислить целевую функцию для всех элементов популяции.

5. Отобрать в соответствии с принципом рулетки наиболее адаптированных представителей для формирования следующего поколения.

6. Выполнить кроссовер для формирования следующего поколения.

7. Заменить старую популяцию на новую, увеличить счетчик поколений N=N+1.

8. Выполнить мутацию с помощью назначения вероятностей (P_m~0,001 для любого объекта)

9. Если N=N_max, то выдать лучший объект и закончить алгоритм, иначе (N<N_max) идем к шагу 4.

Сегодня термином генетические алгоритмы называют не одну модель, а достаточно широкий класс алгоритмов. ГА – универсальный метод решения задачи методов оптимизации.

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

Стандартным называется генетический алгоритм, в котором:

· хромосомы представляются битовыми строками

· используется принцип пропорционального отбора выбора родителей

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

Схема ГА.

ГА – адаптивный метод поиска, применяемый для решения задач функциональной оптимизации. Каждая хромосома оценивается мерой её «приспособленности» (fitness function) – в методах оптимизации – целевая функция. Наиболее приспособленные особи получают возможность воспроизвести потомство с помощью «перекрёстного скрещивания». Наименее приспособленные особи постепенно исчезают из популяции в процессе эволюции.

Создание популяции (инициализация)

Отбор

Размножение

Мутация

Рисунок 6 Общая схема ГА