Генетические алгоритмы в изобретательских задачах
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
ие алгоритмы
Эволюционный процесс реализуется за счет способности лучших хромосом оказывать большее влияние на состав новой популяции посредством длительного выживания и более многочисленного потомства. Основные этапы процесса эволюции, на основе которого создаются нужные схемы генетического поиска, согласно Д. Холланду следующие:
. Конструирование начальной популяции. Ввести точку отчета поколений t = 0. Вычислить приспособленность хромосом популяции, а затем среднюю приспособленность популяции.
. Установление t = t + 1. Выбрать двух родителей (хромосом) для кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.
. Формирование генотипа потомка. С заданной вероятностью произвести над генотипами выбранных хромосом кроссинговер. Выбрать с вероятностью 0,5 один из потомков p(t) и сохранить его как члена новой популяции. Последовательно применить к р(t) оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохранить как p(t).
. Отбор хромосомы случайным образом для исключения ее из популяции. Обновление текущей популяции заменой отобранной хромосомы на p(t).
. Определение приспособленности (целевой функции) p(t) и пересчет средней приспособленности популяции.
. ЕСЛИ t = tзаданному, то переход к 7, если нет, то переход к 2.
. Конец работы.
Мы привели так называемый репродуктивный план Д. Холланда в несколько упрощенном виде. Заметим, что в технических задачах оптимизации часто вместо понятия приспособленность используют понятие целевая функция. Биологи называют эту функцию - fitnessfunction. Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Он копирует последовательности и переставляет их части. Предварительно ПГА случайно генерирует популяцию последовательностей - хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем он применяет множество простых операций к начальной популяции и генерирует новые популяции.
ПГА состоит из трех операторов:
репродукции;
кроссинговера (ОК);
мутации (ОМ).
.3 Пример
Рассмотрим классическую изобретательскую задачу о запайке ампулы с лекарством. Имеется ампула с жидким лекарством, которая установлена вертикально капилляром вверх и движется по транспортеру в кассете с другими ампулами. В определенном месте транспортер останавливается, к капиллярам ампул придвигаются газовые горелки, капилляры оплавляются и герметизируют ампулу (рисунок 15). Здесь можно сформулировать техническое противоречие: если длина пламени большая, тогда запайка хорошая, но место лекарство перегревается и портится, если длина пламени маленькая, тогда запайка плохая, но лекарство не портится. Цель задачи - найти некий ресурс - икс-элемент, который позволит разрешить это противоречие и обеспечит как хорошую запайку ампулы, так и сохранность лекарства.
Рисунок 15 - Запайка ампул с лекарством
Составим структурную потоковую схему преобразования энергии и информации (рисунок 16).
Рисунок 16 - Потоковая структурная схема
По схеме определяем, какие вещества и поля следует учитывать при решении задачи, а затем, - какие ресурсы (факторы) выбрать для описания этих веществ и полей. Чем больше факторов мы выберем, тем больше информации о задаче получит алгоритм поиска, и тем эффективнее он будет работать. В этом отличие генетического алгоритма от АРИЗ. АРИЗ строит модель задачи в виде противоречия для одного, узкого места структуры. Например, в рассматриваемой задаче узкое место - это пара пламя-ампула (лекарство), все остальные вещества и поля с их свойствами исключаются из модели. Хорошая запайка оценивается длиной оплавленной части капилляра, а порча лекарства - температурой пламени. Скрещивание двух факторов - длины и температуры дает лишь один родительский тренд.
Использование же генетического алгоритма позволяет использовать структурную модель более широко, предположив в ней наличие многих противоречий в виде бинарных отношений свойств веществ и полей. Благодаря этому появляется несколько родительских трендов. Если скрещивание выводит особь на нереализуемый в трехмерном пространстве тренд, то она (особь) скрещивается с третьим фактором, возвращающим потомка на реализуемый тренд, т.е. в этом случае используются уже тернарные отношения между свойствами.
Выберем следующие факторы, разнородно влияющие на качество запайки ампулы:
.температура пламени;
.температура лекарства;
.давление в горелке;
.объем ампулы;
.длина (высота) ампулы;
.длина капилляра ампулы;
.длина (диаметр) сопла горелки;
.длина (толщина) стенок ампулы:
.теплоемкость стекла;
. время запайки.
Теперь эти факторы мы должны скрестить. Для этого разобьем факторы попарно и логически перемножим их физические размерности по формуле(3). Результат приведен в таблице 2.
Таблица 2 - Факторы, влияющие на запайку ампулы
Входной фактор, хВходной фактор, yВыход, zСумма показателей степеней m+nДлина, L1T0Длина, L1T0L2T02Длина, L1T0Время, L0T1L1T12Время, L0T1Время, L0T1L0T22Время, L0T1Температура, L5T-4L5T-32Длина, L1T0Температура, L5T-4L6T-42Температура, L5T-4Температура, L5T-4L10T-82Давление, L2T-4Теплоемкость, L0T-2L2T-6-4Объем, L3T0Длина, L1T0L4T04
Расчет показал, что родительский тренд для задачи о запа?/p>