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

Эволюционный процесс реализуется за счет способности «лучших» хромосом оказывать большее влияние на состав новой популяции посредством длительного выживания и более многочисленного потомства. Основные этапы процесса эволюции, на основе которого создаются нужные схемы генетического поиска, согласно Д. Холланду следующие:

. Конструирование начальной популяции. Ввести точку отчета поколений t = 0. Вычислить приспособленность хромосом популяции, а затем среднюю приспособленность популяции.

. Установление t = t + 1. Выбрать двух родителей (хромосом) для кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.

. Формирование генотипа потомка. С заданной вероятностью произвести над генотипами выбранных хромосом кроссинговер. Выбрать с вероятностью 0,5 один из потомков p(t) и сохранить его как члена новой популяции. Последовательно применить к р(t) оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохранить как p'(t).

. Отбор хромосомы случайным образом для исключения ее из популяции. Обновление текущей популяции заменой отобранной хромосомы на p'(t).

. Определение приспособленности (целевой функции) p'(t) и пересчет средней приспособленности популяции.

. ЕСЛИ t = tзаданному, то переход к 7, если нет, то переход к 2.

. Конец работы.

Мы привели так называемый репродуктивный план Д. Холланда в несколько упрощенном виде. Заметим, что в технических задачах оптимизации часто вместо понятия «приспособленность» используют понятие «целевая функция». Биологи называют эту функцию - fitnessfunction. Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Он копирует последовательности и переставляет их части. Предварительно ПГА случайно генерирует популяцию последовательностей - хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем он применяет множество простых операций к начальной популяции и генерирует новые популяции.

ПГА состоит из трех операторов:

• репродукции;

• кроссинговера (ОК);

• мутации (ОМ).

.3 Пример

Рассмотрим классическую изобретательскую задачу о запайке ампулы с лекарством. Имеется ампула с жидким лекарством, которая установлена вертикально капилляром вверх и движется по транспортеру в кассете с другими ампулами. В определенном месте транспортер останавливается, к капиллярам ампул придвигаются газовые горелки, капилляры оплавляются и герметизируют ампулу (рисунок 15). Здесь можно сформулировать техническое противоречие: если длина пламени большая, тогда запайка хорошая, но место лекарство перегревается и портится, если длина пламени маленькая, тогда запайка плохая, но лекарство не портится. Цель задачи - найти некий ресурс - икс-элемент, который позволит разрешить это противоречие и обеспечит как хорошую запайку ампулы, так и сохранность лекарства.

Рисунок 15 - Запайка ампул с лекарством

Составим структурную потоковую схему преобразования энергии и информации (рисунок 16).

Рисунок 16 - Потоковая структурная схема

По схеме определяем, какие вещества и поля следует учитывать при решении задачи, а затем, - какие ресурсы (факторы) выбрать для описания этих веществ и полей. Чем больше факторов мы выберем, тем больше информации о задаче получит алгоритм поиска, и тем эффективнее он будет работать. В этом отличие генетического алгоритма от АРИЗ. АРИЗ строит модель задачи в виде противоречия для одного, «узкого» места структуры. Например, в рассматриваемой задаче «узкое» место - это пара пламя-ампула (лекарство), все остальные вещества и поля с их свойствами исключаются из модели. Хорошая запайка оценивается длиной оплавленной части капилляра, а порча лекарства - температурой пламени. Скрещивание двух факторов - длины и температуры дает лишь один родительский тренд.

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

Выберем следующие факторы, разнородно влияющие на качество запайки ампулы:

. температура пламени;

. температура лекарства;

. давление в горелке;

. объем ампулы;

. длина (высота) ампулы;

. длина капилляра ампулы;

. длина (диаметр) сопла горелки;

. длина (толщина) стенок ампулы:

. теплоемкость стекла;

. время запайки.

Теперь эти факторы мы должны скрестить. Для этого разобьем факторы попарно и логически перемножим их физические размерности по формуле(3). Результат приведен в таблице 2.