Дискретная математика & математическая логика

Подставляем в правую часть первого уравнения вместо х2 второе уравнение, а во второе вместо х1 – первое:

Таким образом, упорядочивая переменные, получим

Подставим первые два уравнения в третье:

141

Легко видеть, что при данном значении х3 наименьшее f получим при нулевых х4, х5. Это очевидно, поскольку х4, х5 – количество лишних заготовок. При возрастании х3 f будет убывать, но рост х3 ограничивается требованием положительности х4, х5.

Пусть х4 = х5 = 0:

При возрастании х3 отрицательное значение примет прежде всего х1, так как

142

Необходимо убрать в первом уравнении х3, во втором – х2. Подставляем в правую часть первого уравнения вместо х3 второе уравнение, а во второе вместо х2 – первое:

143

144

Видим, что минимальное значение f получим в случае, если х1 = х4 = х5 = 0, при этом зависимые переменные х2, х3 будут положительны:

Таким образом, решение имеет вид

Но нам нужно целочисленное решение! Нетрудно убедиться, что для такого решения

f ≥ 1 (8000)= 727, 2..., 11

или даже f ≥ 728, так как число листов должно быть целым.

Можно ожидать, что такое решение мы получим, если немного изменим решение:

145

Таким образом, для выполнения заказа необходимо доставить со склада 728 листов и 91 из них кроить по второму, а остальные – по третьему способу.

4.5. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ОПТИМИЗАЦИИ

Генетический алгоритм оптимизации – это эвристический алгоритм поиска, используемый для решения задач оптимизации

имоделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию [5]. Генетический алгоритм является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивание», который производит операцию рекомбинации решений-кандидатов, что аналогично скрещиванию в живой природе.

Отцом-основателем генетических алгоритмов считается Джон Холланд (John Holland), книга которого «Адаптация в естественных

иискусственных системах» является основополагающим трудом в этой области исследований.

146

Задача кодируется таким образом, чтобы ее решение могло быть представлено в виде вектора («хромосомы»). Случайным образом создается некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определенное значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются векторы («селекция»), допущенные к «скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» – crossover и «мутация» – mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторыит.д.

Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть:

–нахождение глобального либо субоптимального решения;

–исчерпание числа поколений, отпущенных на эволюцию;

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

решений в очень больших, сложных пространствах поиска.

Таким образом, можно выделить следующие этапы генети-

ческого алгоритма:

–создание начальной популяции;

–вычисление функций приспособленности для особей популяции (оценивание);

–начало цикла;

–выбор индивидов из текущей популяции (селекция);

–скрещивание и/или мутация;

–вычисление функций приспособленности для всех особей;

–формирование нового поколения.

Если выполняются условия остального, то «конец цикла», иначе «начало цикла».

147

Чтобы применить генетический алгоритм к задаче, сначала выбирается метод кодирования решений в виде строки. По существу, такая кодировка соответствует разбиению пространства параметров на гиперкубы, которым соответствуют уникальные комбинации битов встроке-хромосоме. Для установления соответствия между гиперкубами разбиения области и бинарными строками, описывающими номера таких гиперкубов, кроме обычной двоичной кодировки использовался рефлексивный код Грея. Код Грея предпочтительнее обычного двоичного тем, что обладает свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменениюкодовойкомбинациитольководномразряде.

Рассмотрим пример кодирования для генетического алгорит-

ма (табл. 4.1).

Таблица 4 . 1

Пример кодирования вариантов для генетического алгоритма

148

Стандартные операторы для всех типов генетических алгоритмов – это селекция, скрещивание и мутация.

Оператор селекции (reproduction, selection) осуществляет от-

бор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир.

Метод рулетки (roulette-wheel selection) отбирает особей с помощью n запусков рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален соответствующей величине Psel(i), вычисляемой по некоторой формуле.

Турнирный отбор (tournament selection) реализует n турни-

ров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k = 2.

Оператор скрещивания (crossover) осуществляет обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным. Одноточечный кроссовер работает следующим образом. Сначала случайным образом выбирается одна из (l −1)-x точек разрыва. Точка

разрыва – участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем соответствующие сегменты различных родителей склеиваются – и получаются два генотипа потомков.

Одноточечный оператор скрещивания (точка разрыва равна трем) показан на рис. 4.11.

Рис. 4.11. Одноточечный оператор скрещивания

149

Мутация (mutation) – стохастическое изменение части хромосом. Каждый ген строки, которая подвергается мутации, с вероятностьюPmut (обычнооченьмаленькой) меняетсяна другойген(рис. 4.12).

Рис. 4.12. Мутация

Алгоритм работы классического генетического алгоритма приведен на рис. 4.13.

Рис. 4.13. Классический генетический алгоритм

В 1992 году была предложена идея генетического программирования. Оно строится с опорой на концепцию генетических алгоритмов. В отличие от генетических алгоритмов, в генетическом программировании все операции производятся не над строками, а над деревьями. При этом используются те же операторы – селекция, скрещивание и мутация [5].

150