Благодарю автора за ответственное отношение к выполнению заказа.
Информация о работе
Подробнее о работе
Интеллектуальные информационные системы
- 38 страниц
- 2016 год
- 129 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Введение
Задача однопараметрической оптимизации всегда имеет наилучшее решение, дающее максимальное возможное значение оптимизируемой функции при заданных ограничениях. Возможно, максимум достигается на нескольких различных конфигурациях системы. В любом случае, наилучшее значение можно найти полным перебором всех вариантов. В случае рассматриваемой в работе оптимизации по нескольким критериям ситуация иная: если параметры считаются равнозначными, то могут существовать не сравнимые между собой решения, такие что одно лучше по одному параметру, второе — по другому.
Для решения задачи многокритериальной оптимизации существуют две большие группы методов [1]:
I. Введение искусственной возможности сравнения любых решений. В этом случае задача по сути сводится к однопараметрической.
II. Отказ от поиска единственного лучшего решения, и вместо этого поиск набора решений, которые лучше остальных, но не сравнимы между собой. В этих методах используется концепция Парето-доминирования. Алгоритмы данной группы выдают в качестве результата множество Парето, либо некоторое его приближение.
В данной работе исследуются алгоритмы второй группы. Сравнение алгоритмов первой и второй группы между собой не представляется возможным. Поэтому в дальнейшем алгоритмы первой группы рассматриваться не будут.
Если нужно найти часть множества Парето с помощью приближенного метода, это значит, что требуется получить некоторое множество решений, которое обладает следующими свойствами [11]:
• Близко к реальному множеству Парето.
• Распределено вдоль реального множества Парето равномерно.
• Достигает границ реального множества Парето.
О формализации этих критериев речь пойдет далее, в разделе 7.
Наиболее тривиальный алгоритм — случайный поиск, когда на каждой итерации выбирается случайное решение, а результатом работы являются все недоминируемые решения среди рассмотренных на всех итерациях. Очевидно, такой алгоритм не может гарантировать, что результат будет обладать указанными выше свойствами. Далее будут рассмотрены различные алгоритмы, которые нацелены на получение результатов, более близких к реальному Парето-фронту.
СОДЕРЖАНИЕ
стр
Введение 3
1 PAES (Pareto achieved evolution algorithm) 5
2 Nondominated sorting genetic algorithm (NSGA) 10
3 Strength Pareto Evolutionary Algorithm (SPEA) 12
4 Improved Strength Pareto Evolutionary Algorithm (SPEA-2) 13
5 Pareto Envelope-Based Selection Algorithm (PESA) 15
6 Метод взвешенных сумм (WO) 16
7 Программа 16
8 Описание экспериментального исследования 23
9 Результаты исследования 27
Заключение 33
Литература 37
Заключение
В рамках данной работы получены следующие результаты:
• Изучены и описаны в обзоре методы многокритериальной оптимизации, выдающие в качестве решения Парето-фронт.
• Среди обозреваемых алгоритмов выбраны и адаптированы для рассматриваемой задачи ряд алгоритмов:PAES, NSGA, NPGA, VEGA, PESA, SPEA, SPEA-2, случайный поиск.
• Реализованы алгоритмы и программное средство для проведения экспериментов.
• Проведено экспериментальное исследование выбранных алгоритмов
Установленные важные свойства конкретных алгоритмов:
• SPEA-2 и PESA — два наиболее эффективных алгоритма для исследуемой задачи.
• Следом за ними по качеству идут NPGA, VEGA и PAES.
• Алгоритм SPEA малоэффективен из-за неподходящей к рассматриваемой задаче функции отбора.
В качестве дальнейшего развития данной темы можно выделить следующие направления:
• Изучение влияния начального приближения на результат генетических алгоритмов.
• Исследование работы алгоритмов при различных настройках.
• Создание гибридных алгоритмов, комбинирующих свойства описанных в обзоре на разных стадиях работы или изменяющих параметры в процессе работы.
• Исследование алгоритмов многокритериальной оптимизации, выдающих единственное решение.
Литература
[1] C.A.Coello A Comprehensive Survey Of Evolutionary-Based Multiobjective Optimization Techniques. Knowledge and Information Systems, vol. 1, no. 3, pp. 269-308, 1999
[2] D.W.Coit, T. Jin, N. Wattanapongskorn System Optimization With Component Reliability Estimation Uncertainty: A Multi-Criteria Approach. IEEE Trans. Reliability 53, pp. 369-380, 2004.
[3] Corne, D. W., J. D. Knowles, and M. J. Oates (2000). The pareto envelope-based selection algorithm for multiobjectiveoptimisation. In M. S. et al. (Ed.), Parallel Problem Solving from Nature - PPSN VI, Berlin, pp. 839-848. Springer.
[4] Deb, K., S. Agrawal, A. Pratap, and T. Meyarivan (2000). A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In M. S. et al. (Ed.), Parallel Problem Solving from Nature - PPSN VI, Berlin, pp. 849-858. Springer.
[5] J.Horn, N.Nafpliotis, D.E.Goldberg A niched Pareto genetic algorithm for multiobjective optimization. Proceedings of the First IEEE Conference on Evolutionary Computation, Z. Michalewicz, Ed. Piscataway, NJ: IEEE Press, 1994, pp. 82-87.
[6] J.Knowles, D.CorneThe Pareto achieved evolution strategy: A new baseline algorithm for Pareto multiobjectiveoptimizatio. Congress on Evolutionary Computation (CEC99), Volume 1, Piscataway, NJ, pp. 98-105. IEEE Press
[7] H. A. Taboada, FatemaBaheranwala, David W. Coit Practical solutions of multi- objective system reliability design problems using genetic algorithm. (2006).. Reliability
Engineering &System; Safety, 92(3), 314-322
[8] N. Wattanapongskorn, S.P.Levitan Reliability Optimization Models for Embedded Systems With Multiple Applications. IEEE Transactions on Reliability, vol. 53, issue. 3, Sept. 2004, pp. 406 - 416
[9] N. Wattanapongskorn, D.W. Coit Fault-Tolerant embedded system design and optimization considering reliability estimation uncertaint. Reliability Engineering and System Safety, 2007, pp. 395-407.
[10] E.Zitzler, L.ThieleMultiobjective Evolutionary Algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. Evol. Comput., vol. 3, pp. 257-271, Nov. 1999.
[11] М. Мину. Математическое программирование. Теория и алгоритмы.- М.: Наука, 1990.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
