II. Двоичный/непрерывный ГА
ГА, описанный в данной статье, минимизирует затратные функции, которые при вычислении затрат оперируют действительными и целыми переменными. Для повышения универсальности ГА все переменные картируются (распределяются) по непрерывным значениям от 0 до 1. Термином непрерывный мы пользуемся вместо действительный, поскольку последний подразумевает значения в интервале ±?, а первый в настоящей работе соответствует значениям от 0 до 1.
Матрица совокупностей npop x nvar для данного ГА представлена Уравнением 1, где vm,n = переменной n в конфигурации (хромосоме) m при 0 ? vm,n ? 1. Каждый ряд соответствует хромосоме; значения первоначально создают с помощью однородного произвольного генератора чисел. Непрерывная переменная vm,n преобразуется либо в действительную переменную xn, в целое In, либо в двоичное bn. Смотри Ур.2, где min и max представляют границы переменной, xmin ? xn ? xmax; rounddown - функция, которая округляет до следующей меньшей целой; а round - функция, которая округляет до ближайшей целой. Как и в двоичном ГА, группа двоичных знаков образует ген (последовательность). Преимуществом данного подхода является то, что все масштабирование, квантование и округление происходит внутри затратной функции, так что ГА действует независимо от типа переменной. Поскольку операторы работают с любым сочетанием типов переменных, нет необходимости использовать двоичный ГА, действительный ГА и ГА со смешанными целыми. В хромосоме может быть любое сочетание действительных, целых и двоичных переменных.
Продолжительность существования конфигурации (хромосомы) можно обеспечить с помощью ряда разных способов. В данном случае в фонде скрещивания сохраняются верхние 50% хромосом. Мы используем турнирный отбор при участии в одном турнире двух хромосом. Почти те же результаты дает выбор по правилам рулетки в сочетании с расстановкой по рангам [9].
Теперь можно выполнить скрещивание двух выбранных хромосом за счет одного из многих различных двоичных скрещиваний или скрещиваний на основе действительного ГА [9]. Однородное скрещивание дает большие возможности исследования области затрат, чем другие подходы к скрещиванию [9]; как раз оно и реализовано в этом алгоритме. Вначале создают произвольный двоичный шаблон. Единица в его колонке означает, что результат (потомок) наделен переменным значением в графе parent#1 (родитель#1). Если там будет 0, то результат наделен переменным значением в графе parent#2 (см. Ур.3). При таком подходе от каждой выбранной пары родителей создается только один потомок. Если значения являются двоичными, то такой тип скрещивания дает разнообразие результатов, а если они целые или непрерывные, то лишь обменивает значения у хромосом. Далее благодаря мутации в рамках совокупности непрерывных значений появляются новые значения. В таком алгоритме также хорошо действует непрерывное скрещивание.
Один из подходов к мутации заключается в произвольном выборе переменных в совокупности и замене их однородными произвольными значениями. Другим подходом является введение произвольного поправочного коэффициента. Такой коэффициент можно создать путем умножения каждого элемента хромосомы на произвольное число (-1 ? вrm ? 1) и далее умножением всей хромосомы на коэффициент мутации (0 ? бr ? 1). Смотри Ур.4, где rem - функция остатков (разряды слева от десятичной точки опускаются). Такой вид мутации приводит к изменению всей хромосомы, а не отдельной переменной.
В попытке определить подходящий размер совокупности и бr были проведены испытания алгоритма на двух затратных функциях. В обоих случаях ГА завершал работу после 400 оценок функций и показывал самые благоприятные результаты. Первой тестовой функцией была (Ур.5), имеющая минимум нуля при xn = 0. Результаты усреднили по 100 прогонам при размере совокупности от 8 до 96 и частоте мутации от 0,01 до 0,3. Наилучшие результаты были при размере совокупности 8 и частоте мутации 0,1. Второй тестовой функцией была (Ур.6), имеющая минимум нуля при xn = 0. Результаты усреднили по 500 прогонам при размере совокупности от 8 до 96 и частоте мутации от 0,005 до 0,3. Наилучшие результаты были при размере совокупности 40 и частоте мутации 0,01.