WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 |   ...   | 2 | 3 ||

Сегрегированный генетический алгоритм был представлен Ле Ришем (Le Riche). В данном методе используется два штрафа p1 и p2 в двух разных популяциях. Цель – попытаться избежать проблемы слишком больших или слишком малых штрафов. Для этого и используется две популяции, функция полезности в которых рассчитывается с использованием малого p1 и большого p2 штрафов. Проблемой данного метода является неопределенность способа выбора штрафных функций. Для тестирования сегрегированного генетического алгоритма был использован метод статических штрафных функций Кури Моралеса и Кузеда, описанный ранее. Также для объединения двух популяций в одну кроме стандартных операторов, определенных ниже, был применен оригинальный метод, предложенный Ле Ришем, который можно определить как стратегия элитизма с коэффициентом 0,5. Т.е. в следующую популяцию попадают по половине лучших особей из двух исходных популяций.

Метод восстановления недопустимых индивидов к допустимым основан на функции, которая способна привести непригодный по ограничениям индивид к пригодному путем изменения его хромосомы. Особенность метода состоит в том, что функции восстановления могут существенно различаться, соответственно может существенно различаться эффективность работы алгоритма. В качестве еще одной особенности можно отметить то, что некоторая часть восстановленных индивидов может заменять родителей в популяции. Процент таких индивидов может варьироваться от 0 % до 100 %. Орвош (Orvosh) и Дэвис (Davis) определили так называемое правило 5 %, в соответствии с которым наибольшую эффективность алгоритм имеет тогда, когда 5 % восстановленных особей заменяют своих родителей в популяции. Для исследования данного метода было использовано правило 5 %, а также функция восстановления, которая поочередно исключает из непригодного индивида случайный проект до тех пор, пока он не станет пригодным.

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

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

Для исследования различных стратегий выбора индивида в качестве оператора выбора родителей использовались метод рулетки, панмиксия, инбридинг, аутбридинг; в качестве оператора отбора особей в новую популяцию использовались отбор усечением, метод Больцмана, стратегия элитизма + новые особи, стратегия элитизма + метод Больцмана. В качестве метрики различия индивидов для использования в операторах инбридинга и аутбридинга использовалось расстояние Хэмминга, которое определяется как число различающихся разрядов в бинарной хромосоме.

Генетические алгоритмы оценивались по следующим критериям: время выполнения алгоритма, соответствие полученного результата оптимуму функции полезности. Выбор именно таких критериев обусловлен изначальной нацеленностью исследования на дальнейшее прикладное применение при разработке программного комплекса «Автоматизированной системы управления процессом формирования портфеля инновационных проектов».

Параметры генетического алгоритма были следующие: количество поколений – 1000, количество особей в поколении – 20, вероятность мутации – 0,1, вероятность кроссовера – 0,8, кроссовер одноточечный, для отбора усечением порог 0,8, коэффициент элитизма (часть элитных особей, остающихся в популяции) – 0,1. Количество итераций при тестировании – 100. Количество проектов в тестовой модели – 5, количество агентов – 2, горизонт планирования – 12 месяцев.

Как показало исследование среди выбранных методов лучше всего справляется с задачей поиска оптимума функции полезности метод отброса недопустимых индивидов (эффективность 80 %, время выполнения 23,3588 с), вторым по эффективности является метод восстановления недопустимых индивидов к допустимым (эффективность 79 %, время выполнения 30,2101 с). Методы, основанные на штрафных функциях, и сегрегированный генетический алгоритм не показали достаточно хороших результатов. Возможно, это объясняется тем, что в задаче велико количество ограничений. По-видимому, для данного типа задач наиболее важно максимально расширить область поиска. В этом случае увеличивается вероятность попадания в оптимум. Об этом говорит тот факт, что наилучшие результаты были достигнуты при применении в качестве оператора выбора родителей аутбридинга, а в качестве оператора отбора особей в новую популяцию стратегии элитизма в совокупности с генерацией новых индивидов. Аутбридинг и ввод новых индивидов в популяцию нацелены на расширение области поиска, а стратегия элитизма способствует закреплению найденных хороших индивидов. Следует также отметить, что достаточно хорошие результаты были получены при использовании метода восстановления с рулеточным отбором родительской пары в совокупности с той же стратегией элитизма и генерацией новых индивидов (эффективность 70 %, время выполнения 29,6522 с).

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

На начальном этапе исследования было определено влияние коэффициента элитизма на эффективность работы метода. Наибольшего эффекта метод достигает при коэффициенте элитизма от 0,2 до 0,4, далее процент попадания в оптимум падает. Однако при малых значениях коэффициента элитизма алгоритм выполняется дольше всего. Поэтому для дальнейшего исследования было выбрано крайнее значение коэффициента 0,4, при котором эффективность высока, а время выполнения наименьшее.

На рисунке 2 представлены результаты исследования влияния вероятности мутации и кроссовера на время исполнения и эффективность метода при коэффициенте элитизма 0,4.

В результате проведенных исследования было выявлено, что время исполнения алгоритма существенно зависит от вероятности кроссовера и достигает своего максимума при максимальной вероятности кроссовера и мутации, так как в этом случае возрастает количество операций с хромосомой. Наибольшая эффективность метода отмечается при вероятности кроссовера более 0,6 и вероятности мутации до 0,4. Наивысшая эффективность отмечена при вероятности кроссовера, равной 1, и вероятности мутации от 0,1 до 0,4.

Количество поколений во всех упомянутых экспериментах было равно 1000. Для определения распределения номера поколения, в котором впервые появилось оптимальное значение, был проведен эксперимент, состоящий из 100 запусков алгоритма при вероятности мутации 0,2, вероятности кроссовера 1 и коэффициенте элитизма 0,4, результаты которого представлены на рисунке 3.

Рис.2. Зависимость времени исполнения алгоритма от вероятности кроссовера и мутации (слева) и зависимость эффективности алгоритма от вероятности кроссовера и мутации (справа)

Рис.3.Номер поколения, в котором впервые появляется оптимальное значение

Из приведенной диаграммы видно, что в 50 % случаев оптимальное значение функции полезности было получено в течение первых 250 поколений. В течение 500 первых поколений оптимум найден уже почти в 80 % случаев, а уменьшение количества поколений с 1000 до 750 практически никак не повлияет на результативность метода. При этом выигрыш во времени составит 23 % для 750 поколений и 47 % для 500 поколений.

Для сравнения эффективности и скорости работы исследованного генетического алгоритма с наиболее эффективными параметрами с другими методами оптимизации было проведено еще одно исследование. Среди нескольких методов оптимизации были выбраны аддитивный алгоритм Балаша, относящийся к группе методов неявного перебора, и метод ветвей и границ из теории целочисленного программирования. В качестве тестовой задачи была использована задача, с теми же параметрами, что и в предыдущем исследовании, различалось только количество проектов. В генетическом алгоритме применялись в качестве оператора выбора родителей – аутбридинг, в качестве оператора отбора особей в новую популяцию – стратегия элитизма в совокупности с генерацией новых индивидов. Для учета ограничений применялся метод отброса недопустимых индивидов. Параметры генетического алгоритма были следующими: количество поколений – 1000; размер популяции – 20 экземпляров; коэффициент элитизма – 0,4; вероятность кроссовера – 1; вероятность мутации – 0,2.

Зависимость скорости выполнения алгоритмов от количества проектов в задаче приведена на рисунке 4.

Рис.4. Сравнительный анализ скорости выполнения алгоритмов решения задачи формирования портфеля инновационных проектов

Как видно из рисунка 4, при количестве проектов в задаче более 7 как аддитивный алгоритм, так и метод ветвей и границ требуют значительного времени для решения. При этом генетический алгоритм справляется с такой задачей достаточно успешно. Существенное увеличение времени выполнения происходит только при возрастании количества проектов в задачи до 20 и более. Таким образом, можно сформулировать следующие рекомендации при расчетах портфеля инновационных проектов: если в задаче количество проектов не превышает 7, то использовать аддитивный алгоритм Балаша (или метод ветвей и границ), в противном случае использовать генетический алгоритм. Следует отметить, что алгоритм Балаша несколько предпочтительнее метода ветвей и границ за счет своей относительной простоты, а также скорости решения задачи.

В четвертой главе поставлена задача разработки «Автоматизированной системы управления процессом формирования портфеля инновационных проектов» на примере процесса формирования портфеля инновационных проектов. Определены следующие требования к разрабатываемой системе: расширяемость, кроссплатформанность, унифицированность решений, гарантия сохранности и поддержание целостности информационных ресурсов. Принимая во внимание указанные выше требования сделан вывод о том, что система должна быть построена на следующих принципах:

  1. Трехзвенная архитектура.
  2. Централизованное хранение информационной базы данных системы.
  3. Модульный принцип построения системы, в соответствии с детализацией функций каждой из составляющих его подсистем.
  4. Организационно-методическое единство.
  5. Техническая и программная совместимость структурных компонент системы.
  6. Открытость для присоединения новых информационных ресурсов.

Выбраны средства разработки и системное программное обеспечение для АСУ. Выполнен анализ имеющихся методологий проектирования и разработки программного обеспечения и осуществлено проектирование системы на основе унифицированного процесса разработки с привлечением языка моделирования UML, приведены основные UML-диаграммы проекта. Представлены скриншоты программного продукта.

В заключении диссертации изложены основные выводы и обобщения, вытекающие из логики и результатов исследования.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

  1. Денисов А.В., Лябах Н.Н. Система генерации инновационных проектов // Молодые ученые – транспорту–2007: Сб. научн. тр., посв. 170-летию российских железных дорог. – Екатеринбург: УрГУПС. – 2007. (0,07 п.л.)
  2. Денисов А.В. Управление инновационной деятельностью отрасли // Труды всерос. науч.-практ. конф. «Транспорт-2008», часть 1. – Ростов н/Д: РГУПС, 2008. (0,18 п.л.)
  3. Денисов А.В., Лябах Н.Н. Генетические алгоритмы в задачах формирования портфеля инновационных проектов // Сб. науч. трудов V-ой междунар. науч.-практ. конф. «Интегрированные модели и мягкие вычисления в искусственном интеллекте», 2009. – Т.2. (0,22 п.л.)
  4. Денисов А.В. Исследование влияния структуры генетического алгоритма на качество решения задачи формирования портфеля инновационных проектов // Труды РГУПС, 2009. – №1. (0,58 п.л.)
  5. Денисов А.В. Исследование генетического алгоритма в контексте решения задачи формирования портфеля инновационных проектов // Труды всерос. науч.-практ. конф. «Транспорт-2009», часть 1. – Ростов н/Д: РГУПС, 2009. (0,16 п.л.)
  6. Денисов А.В. Автоматизированная система управления портфелем проектов организации // СПИСОК-2009: материалы межвуз. науч. конференции по проблемам информатики, 20-23 апр. 2009 г., Екатеринбург. (0,12 п.л.)
  7. Денисов А.В. Эффективность генетического алгоритма для решения задачи формирования портфеля инновационных проектов // СПИСОК-2009: материалы межвуз. науч. конференции по проблемам информатики, 20-23 апр. 2009 г., Екатеринбург. (0,11 п.л.)
  8. Денисов А.В., Шабельников В.А., Сарьян А.С. Система мониторинга и анализа состояния искусственных сооружений на железнодорожном транспорте // Молодой ученый, 2009 г. – №8. (0,2 п.л.)

Публикации в изданиях, рекомендованных ВАК:

  1. Денисов А.В., Лябах Н.Н. Автоматизированная система управления научно-техническим развитием ОАО «РЖД» // Автоматика, связь, информатика, 2007. – №11. (0,13 п.л.)
  2. Денисов А.В. Оценка компетентности эксперта в экспертной системе // Журнал ОПиПМ, 2009. – т.16, в.1. (0,06 п.л.)
  3. Денисов А.В., Лябах Н.Н. Алгоритмическое, математическое, информационное обеспечение формирования портфеля инновационных проектов // Известия вузов. Сев.-Кавк. регион. Техн. науки. – №1, 2009. (0,41 п.л.)
  4. Денисов А.В. Теоретико-прикладные аспекты реализации системы формирования портфеля инновационных проектов // Вестник РГУПС, 2009 г. – №2. (0,65 п.л.)

Личный вклад автора в работах, выполненных в соавторстве

/1, 3, 9, 11/ – разработка алгоритмов функционирования, математического обеспечения, проведение имитационного эксперимента, сбор данных и аналитические расчеты; /8/ – постановка задачи.

Денисов Андрей Витальевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ

Pages:     | 1 |   ...   | 2 | 3 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»