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

Постановка задачи поиска оптимальных решений с помощью генетических алгоритмов

Для применения Генетических алгоритмов необходимо:

1. Выделить совокупность свойств объекта, характерных внутренними параметрами и влияющих на его полезность, т. е. выделить множество управляющих параметров X=(x₁, x₂, ... , x_n). Среди x типов могут быть величины различных типов. Наличие символьных величин обуславливает возможность решения задач не только пар-ой, но и структурной оптимизации.

2. Сформулировать количественную оценку полезности вариантов объектов – функцию F.

Если в исходном виде задача многокритериальная, то такая формулировка означает вывод скалярного критерия.

3. Разработать математическую модель объекта, представляющей собой алгоритм вычисления F для X.

4. Представить Х в форме хромосомы – записи вида: х₁ х₂ х₃ ... х_n

Используется следующая терминология:

Ген- управляемый параметр х;

Аллель – значение гена;

Локус - позиция, занимая геном в хромосоме;

Генотип – экземпляр хромосомы, представляющий собой совокупность внутренних параметров, проектируемого с помощью генетических алгоритмов объекта;

Генофонд – множество всех возможных генотипов;

Фенотип – совокупность генотипа и соответствующего значения F;

Под фенотипом понимают совокупность выходных пар-в, синтезируемого с помощью генетических алгоритмов объектов.

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

Генерация выполняется случайным выбором аллеями каждого гена. Далее организуется циклический процесс смены поколений.

for ( k =0; k <G; k++)

for ( j=0; j<N; j++)

{Выбор родительской пары хромосом}

Кроссовер

Мутации

Оценка F

Селекция

{Замена текущего поколения новым}

G – число повторений внешнего цикла.

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

На внутреннем цикле повторяется операция выбора родителей, кроссоверы, мутации, оценки приспособленности потомков, селекции хромосом.

Рассмотрим алгоритм выполнения операторов в простом г.а.