Интеллектуальные информационные системы. Дубровин А.Д. - 172 стр.

момента, например, когда приращение целевого качества (полная первая производная
целевой функции) начинает замедляться.
       Описанный алгоритм группового учета аргументов относится к разряду
эволюционных. Его можно представить как следующую последовательность шагов.
   Шаг 1. Выбирается исходная популяция (ИП) из N образцов с разными степенями
проявления нужных свойств. Вычисляется значение целевой функции Ф ИП качества для ИП.
   Шаг 2. Константе С (номер селекции) присваивается значение 1.
   Шаг3. Составляются         N 2 всевозможных сочетания пар образцов популяции и
скрещиваются между собой. Из полученных в результате скрещивания потомков со
свойствами родительских пар по определенным правилам отбирают М лучших (М-ширина
селекции) и вычисляют значение целевой функции Ф C для данной селекции.
   Шаг 4. Производится сравнение значения Ф ИП со значением Ф C . Если значение функции
в результате селекции «улучшилось», то производятся операции присвоения (N=M и С=С+1)
и переход к шагу 5 иначе – к шагу 1 (выбор новой ИП или поиск ошибки в вычислении
значения ЦФ).
   Шаг 5. Если нет признаков инцухта, то (Ф ИП = Ф C ) и переход к шагу 3 (продолжение
селекции), иначе – селекция завершается тем, что потомок пары, давшей «наилучшее»
значение Ф C , объявляется результатом селекции.
    Как мы видим, здесь налицо все признаки эволюционного алгоритма — отбор (селекция)
и генерация нового поколения.
       Генетический алгоритм является самым известным на данный момент
представителем эволюционных алгоритмов, и по своей сути является алгоритмом для
нахождения глобального экстремума многоэкстремальной функции. Генетический алгоритм
представляет собой модель размножения живых организмов, в которой от родительской
пары рождаются потомки, в разной мере наследующие признаки родителей.
       Целевую функцию такой модели можно представить как функцию от множества
переменных, а задачу моделирования – как отыскание глобального экстремума этой
функции:
                         f(x 1 , x 2 ,…, x N ),
       где аргументы х i – это хромосомы – структуры ядер клеток родителей, являющиеся
носителями их наследственных признаков, а N- общее число хромосом, связанных целевой
функцией.
       Упрощенно можно считать, что хромосомы особей состоят из генов - реально
существующих элементарных (неделимых) и комбинируемых при скрещивании единиц
наследственности. Хромосомы могут содержать разное число генов. Наследственный
аппарат каждой разновидности живого организма содержит разное число разных хромосом.
Каждая хромосома содержит определенный генетический код. Целенаправленно
комбинируя расположением генов в хромосомах двух родителей, можно получать потомство
с «лучшими», чем у родителей свойствами. Гены могут изменяться (мутировать) под
воздействием разных факторов. Мутация генов внутри хромосомы может приводить к
образованию новых хромосом.
       Для того чтобы генетический алгоритм «заработал», необходимо представить
независимые переменные (хромосомы) их кодами. Это коды можно записать в виде целых
чисел, представленных в двоичном формате или чисел в формате с плавающей запятой.
       В случае если мы используем двоичное кодирование, код каждой хромосомы может
потребовать разного числа битов. Если сравнивать эти два способа кодирования, то лучшие
результаты дает вариант представления кодов хромосом в двоичном формате.
       Целью генетического моделирования (постановкой задачи) можно считать создание
(синтез) на основе заданной совокупности хромосом разных родителей устойчивого
потомства с желаемыми свойствами.

                                                                                   207