Генетические алгоритмы в изобретательских задачах
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
?ке ампул задается показателем m+n=2. Кроме того, имеются и другие родительские тренды, полученные перемножением других факторов. Следовательно, в задаче действует целый ряд противоречий, которые можно использовать для нахождения другого решения. Далее нам следует определить, какой из ресурсов на родительском тренде может дать наиболее эффективное решение задачи. Для поиска решения воспользуемся генетическим алгоритмом.
На первом шаге производится инициализация, или выбор исходной популяции особей (таблица 3, второй столбец). В нашей задаче особями являются физические размерности таблицы Бартини (таблица 1). Нам предстоит в ходе искусственной эволюции выбрать среди них наилучшую с точки зрения решения поставленной задачи. Необходимо определить функцию приспособленности каждой особи (таблица 3, третий столбец). Для этого присвоим каждой из них некоторую ценность, выраженную числом в диапазоне от единицы до пяти. Чем больше число, тем более приспособленной является особь. Факторы, непосредственно влияющие на запайку ампулы, обладают наиболее сильной наследственной информацией, поэтому их надо поощрить - придадим им максимальную ценность - пять баллов. Остальные ресурсы пока не несут какой-либо наследственной информации - поэтому оценим их единицей. Анализироваться будут только те величины, которые в таблице имеют физическое определение.
Таблица 3 - Исходнаяпопуляцияособей
Номер особиОсобьФункция приспособленностиСекторГраницы секторов1L3T-511,721,722L5T-511,723,453L1T-411,725,174L2T-458,6213,795L3T-411,7215,526L4T-411,7217,247L5T-458,6225,868L1T-311,7227,599L2T-311,7229,3110L3T-311,7231,0311L4T-311,7232,7612L-1T-211,7234,4813L0T-258,6243,1014L1T-211,7244,8315L2T-211,7246,5516L3T-211,7248,2817L4T-211,7250,0018L5T-211,7251,7219L-1T-111,7253,4520L0T-111,7255,1721L1T-111,7256,9022L2T-111,7258,6223L3T-111,7260,3424L4T-111,7262,0725L-1T011,7263,7926L0T011,7265,5227L1T058,6274,1428L2T011,7275,8629L3T058,6284,4830L4T011,7286,2131L-1T111,7287,9332L0T158,6296,5533L1T111,7298,2834L0T211,72100,00
Далее проверяется условие остановки алгоритма. Примем, что для нашего примера поиска необходимо сделать 5 итераций. Поскольку для исходной популяции ни одного шага алгоритм еще не сделал, то условие остановки не выполнено. Тогда на следующем этапе необходимо провести селекцию особей для скрещивания. Селекция заключается в выборе (по рассчитанным на предыдущем этапе значениям функции приспособленности) тех особей, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют особи с наибольшими значениями функции приспособленности.
Рисунок 17 - Сектора рулетки для всех особей исходной популяции
В задаче для селекции был использован метод рулетки. Каждой особи может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной особи (рисунок 17). Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки.
Все колесо рулетки соответствует сумме значений функции приспособленности всех особей. Каждой особи, обозначаемой chi для i=1,2,…N (где Nобозначает численность популяции), соответствует сектор колеса ?(chi), выраженный в процентах согласно формуле:
(6)
(7)
причем- значение функции приспособленности особи -, а- вероятность селекции особи .
Селекция особи может быть представлена как результат поворота колеса рулетки, поскольку выигравшая, т.е. выбранная особь относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность победы соответствующей особи. Поэтому вероятность выбора данной особи оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор особи можно отождествить с выбором числа из интервала [а, b], где а и b обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что0< а < b < 100. В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса.
Согласно описанному методу для каждой особи текущей популяции (в нашем случае - исходной популяции) получаем секторы колеса рулетки, выраженные в процентах (таблица 3, четвертый столбец). Приведем пример расчета сектора колеса рулетки ?(ch1)для первой особи популяции L3T-5. Вычислим сумму функций приспособленности всех особей популяции:
(8)
Далее рассчитаем вероятность селекции первой особи по формуле (7) . Сектор колеса рулетки, соответствующий первой особи, по формуле (6) равен: Аналогичный расчет делает для всех остальных особей популяции. Результаты приведены в четвертом столбце таблицы 3. То есть мы последовательно отмеряем каждой особи ее часть на колесе рулетки. Распределение секторов по колесу рулетки приведено на рисунке 17, каждый сектор подписан соответствующим номером особи.
Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т. е. на конкретную особь. Выберем из нашей популяции методом рулетки 34 пары особей. Поясним: пусть на рулетке выпадает число 61, оно располагается промежутке от 60,34до 62,07, этому промежутку соответствует особь L4T-1- физическая размерность скорости смещения объема - это первая особь родительской пары. Дал