Модификация эволюционного алгоритма

Для достижения поставленной цели были разработаны и протестированы 7 модификаций стандартного генетического алгоритма (генетические алгоритмы с автоматической настройкой типа селекции, типа скрещивания, уровня мутации, а также с автоматической настройкой комбинаций селекция + мутация, селекция + скрещивание, мутация + скрещивание, селекция + мутация + скрещивание), в том числе и модификация, обеспечивающая его автоматическую настройку в ходе решения оптимизационной задачи с использованием всех возможных комбинаций настраиваемых параметров (а не только лучших схем, полученных по результатам тестирования алгоритмов статистическими методами). генетический алгоритм Statistica модифицированный Принципы работы предложенных алгоритмов состоит в следующем:

Настройки выбираются случайным образом в соответствии с заданным распределением вероятностей.

Начальные вероятности равны, где z — число алгоритмов (число комбинаций настраиваемых параметров).

На каждом поколении оценивается эффективность применяемых настроек (по средней пригодности порожденных потомков):

.

где _ средняя пригодность порожденных потомков; _ общая пригодность индивидов, полученных i-ым алгоритмом; _ количество индивидов, полученных i-ым алгоритмом; _ число алгоритмов (число комбинаций настраиваемых параметров).

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

.

.

.

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

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

Безусловное выполнение условия нормировки вероятностей.

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