Генетический Алгоритм (га) и Универсальная Схема Эволюции (усэ)
... ощущение близости, общности решаемых инженерами и Природой задач, которое не так давно витало в воздухе, сегодня переросло в уверенность, что мир органических репликантов и мир культурных репликантов, к каковым относятся и научные идеи, развиваются по одинаковым законам, а значит нам есть чему учиться у Природы.1
Перенос механизмов природной эволюции в технику и другие области
Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче:
Классическая задача коммивояжера. Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Уже для N > 20 городов поиск оптимального пути представляет собой сложную задачу.
Имеется инвестиционный капитал, который нужно распределить среди N проектов. Для каждого проекта задана функция зависимости прибыли от объема вложения. Требуется найти наиболее прибыльный вариант распределения капитала, при условии, что заданы минимальный и максимальный объем инвестиций для каждого проекта.
Применение искусственной эволюции к синтезу аналогового активного фильтра. Каждый вариант схемы - индивидуум, потребление энергии, занимаемая площадь, быстродействие и устойчивость к шуму этого варианта – величина приспособленности этого индивидуума. В процессе эволюции приспособленность индивидуумов будет возрастать, т.е. будут появляться все более и более совершенные варианты схем.2
Существует растущая потребность в высокоэффективных антеннах средств связи, приспособленных к требованиям потребителя. Использование генетического алгоритма позволяет сделать предварительное описание желательного функционирования антенны и предоставить компьютеру искать параметры конструкции. Количество информации о конструкции, которое должен задать инженер, может быть минимальным.3
В процессе эволюции конструкции нет ни моделирования, ни анализа микросхемы! Полевой переключатель не запрограммирован на следование цепочке шагов-инструкций; задана исходная конфигурация, а затем ей предоставлена возможность вести себя в соответствии с физикой полупроводников.4
Генетические операторы
Кроссовер является наиболее важным генетическим оператором. Он генерирует новую хромосому, объединяя генетический материал двух родительских. Существует несколько вариантов кроссовера. Наиболее простым является одноточечный. В этом варианте просто берутся две хромосомы, и перерезаются в случайно выбранной точке. Результирующая хромосома получается из начала одной и конца другой родительских хромосом.
001100101110010|11000 |
|
00110010111001011100 |
110101101101000|11100 |
Мутация представляет собой случайное изменение хромосомы (обычно простым изменением состояния одного из битов на противоположное).
00110010111001011000 |
|
00110010111001111000 |
Инверсия инвертирует (изменяет) порядок следования битов в хромосоме путем циклической перестановки (случайное количество раз).
00110010111001011000 |
|
11000001100101110010 |
Модель отбора определяет, каким образом следует строить популяцию следующего поколения. Как правило, вероятность участия индивидуума в скрещивании берется пропорциональной его приспособленности. В любом случае каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность индивидуумов перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучшего из найденных индивидуумов.
В самом общем виде процесс, реализумый ГА, представляется схемой
Рис. 1
С чего начинается использование Генетического Алгоритма
Обращение к Генетическому Алгоритму и его использование обязательно означает, что мы хотим оптимизировать параметры системы, т.е. найти возможно лучший их набор.5 Отсюда, очевидно, следует, что исходный набор параметров интересующей нас системы:
неоптимален с точки зрения функционирования системы.6 При невозможности улучшения эта неоптимальность в конце концов приведет к невыживанию системы - система не пройдет отбор в конкурентной среде.
приводит к низкой величине идеальности (отношение «польза / затраты») системы.7
Обратим внимание на то, что при использовании ГА-подхода все время идет речь о выживании и невыживании популяции каких-либо систем, причем, систем любой природы!
Теперь вспомним причины обращения к Универсальной Схеме Эволюции. Для этих причин можно повторить практически те же, что былы предложены для ГА:
пониженная жизнеспособность системы, т.е. выявление проблемы, угрожающей выживанию системы.
пониженная идеальность системы: выявление пониженной идеальности системы (пониженной величины отношения полезных функций системы к затратным, вредным)
Генетические операторы Мутация и Инверсия на УСЭ представлены на Рис. 2, а генетический оператор Кроссовер на Рис. 3.
Отсюда вполне естественными являются совпадения порядка следования и логики блоков Генетического Алгоритма и Универсальной Схемы Эволюции (Рис. 4).