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

В двух словах, данный алгоритм действует путем перебора множества возможных вариантов решений и упорядочивания их согласно тому, насколько хороши их результаты, какими бы целевыми функциями они ни определялись. Далее, по аналогии с теорией естественного отбора, выживают наиболее приспособленные и репродуцируются в следующем поколении вариантов решений, которое наследует как свойства родительских решений, так и свойства предшествующих поколений. Средняя приспособленность популяции за многие' поколения будет возрастать и приближаться к оптимуму.

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

Алгоритм содержит следующие основные шаги:

Длина гена. Вы должны задать длину гена. Ген — это двоичное представление члена популяции вариантов решений. Каждый член этой популяции характеризуется значением каждой переменной (т. е. значением /для каждого сценарного спектра). Так, если мы принимаем длину гена в двенадцать раз больше количества сценарных спектров, то каждой переменной (т. е. значению j) у нас будет соответствовать по двенадцать бит. Двенадцати битов достаточно для представления величины в интервале от 0 до 4095. Последнее число представляется в виде:

2° + 21 + 22 + ... + 211 = 4095

Возводим 2 в степень 0 и прибавляем 2 в следующей степени, пока не дойдем до степени, равной количеству битов минус 1 (т. е. 11, в данном случае). Если имеется, скажем, три сценарных спектра и на каждый из них мы используем длину в двенадцать битов, то длина гена каждого варианта решения есть 12 * 3 = 36 бит. То есть ген в данном случае — это строка из 36 двоичных битов.

Обратите внимание, что данный способ кодирования двоичных строк подходит только для целых величин. Но мы можем приспособить его и для чисел с плавающей запятой с помощью некоторого постоянного делителя. Так, если мы выберем постоянный делитель равным, скажем, 1000, то сможем представлять числа от 0/1000 до 4095/1000, или от 0 до 4,095, с точностью до 0,001.