Интеллектуальные информационные системы

Если первичная проверка прошла успешно, то можно считать, что алгоритм выдает такие результаты, что сравнение с другими алгоритмами осмысленно (иначе могло бы получиться так, что оба алгоритма очень плохи, и сравнение их между собой высокой ценности не несет).Таким образом, на этой стадии алгоритмы сравниваются непосредственно, без помощи сравнений с результатами полного перебора. Это позволяет проводить эксперименты на более объемных исходных данных, для которых полный перебор занял бы слишком много времени. В качестве способа сравнения по-прежнему используется мераC .Гипотеза ставится следующим образом: проверяется, что результат одного алгоритма лучше результата другого, а конкретно, для алгоритмовA иB : «Вероятность того, что С(A,B)>C(B, A) , не меньшеa » при заданном уровне значимости. Сначала это проверяетсяn раз на одной и той же системе, затем наn различных системах (как было описано в пункте 7.1.2, основные параметры систем фиксированы). Таким образом, проводятся две группы сравнительных тестов, и можно провести параллель между ними и тестами, описанными в пунктах 7.1.1 и 7.1.2.9 Результаты исследования9.1 Тесты на одной системеТесты на проводились на системе со следующими параметрами:Число узлов системы5Доступные механизмы в каждом узлеВсе: None, NVP/1/1, NVP/0/1, RB/1/1Число вариантов программ в узле4Число вариантов аппаратуры в узле3Число запусков алгоритма (n)100Точность (а)0.8Вероятность успеха (a)0.9Уровень значимости(b)0.05Таблица 1: Параметры для тестов на одной системеПосле проведения 100 экспериментов в соответствии с методикой из раздела 7.1 для исследуемых методов получены следующие результаты:МетодЧисло итерацийРазмер популяцииДоля успешных испытаний(%)Пройдена ли проверка гипотезы?Случайный поиск4000-88даNPGA2002079даNSGA2002093даPAES4000-90даPESA2002093даSPEA2002095даSPEA-22002097даVEGA2002083даТаблица 2: Результаты тестов на одной системеЧисло итераций бралось так, чтобы потенциально было рассмотрено число решений одного порядка: либо 200 популяций по 20 решений, либо 4000 решений, с учетом того, что решения могут повторяться.Таким образом, все исследуемые алгоритмы прошли проверку при данных условиях, однако видно, что не все алгоритмы одинаково часто выдают хорошие результаты.9.2 Тест на множестве системНа данном этапе в каждом эксперименте создавалась случайная система. Общие параметры экспериментов следующие:Число узлов системы4Доступные механизмы в каждом узлеПроизвольный набор из: None, NVP/1/1, NVP/0/1, RB/1/1, R/2Число вариантов программ в узле3..4Число вариантов аппаратуры в узле2..4Число запусков алгоритма (n)100Точность ( а )0.6Вероятность успеха (a)0.9Уровень значимости(b)0.05Таблица 3: Параметры для тестов на множестве системДля того, чтобы полный перебор 100 систем мог закончиться в обозримое время, размер систем был уменьшен, соответственно понижен порог точности.Результаты приведены в следующей таблице:МетодЧислоРазмерДоля успешныхПройдена лиитерацийпопуляциииспытаний(%)проверка гипотезы?Случайный поиск4000-84даNPGA2002076даNSGA2002082даPAES4000-83даPESA2002088даSPEA2002087даSPEA-22002090даVEGA2002083даТаблица 4: Результаты тестов на множестве систем9.3 Сравнительные тестыПараметры экспериментов:Число узлов системы20Доступные механизмы в каждом узлеПроизвольный набор из: None, NVP/1/1, NVP/0/1, RB/1/1, R/2Число вариантов программ в узле6Число вариантов аппаратуры в узле6Число запусков алгоритма (n)100Вероятность успеха (a)0.9Уровень значимости(b)0.05Таблица 5: Параметры для сравнительных тестовПоскольку объем результатов слишком велик для того, чтобы их можно было привести в данной работе непосредственно, далее будут приведены усредненные результаты и частные случаи.Следующая таблица получена после прогона каждого из алгоритмов 100 раз на одной и той же системе, созданной генератором по указанным выше параметрам.Числа в ячейках показывают среднее значение мерыC от результатов каждой пары алгоритмов: для каждой упорядоченной пары алгоритмов рассчитаны значенияC (X ,Y) , где X иY — результаты, выданный этими алгоритмами на заданной итерации. В соответствующей ячейке таблицы приведено среднее арифметическое этих значений по всем 100 итерациям.RandomPAESPESAVEGANPGANSGASPEASPEA2RandomX0.00.00.0590.04531.00.7370.004PAES1.0X0.1270.9660.9841.01.00.687PESA1.00.99X1.01.01.01.00.98VEGA1.00.080.021X0.861.00.990.284NPGA0.9950.030.010.393X1.00.960.14NSGA0.0750.2500.840.0X0.0450.0SPEA0.750.000.0930.21861.0X0.026SPEA21.00.760.130.9950.991.01.0XТаблица 6: Результаты сравнительных тестов (1)Следующая таблица аналогична предыдущей, но получена после эксперимента, где на каждой из 100 итераций генерировалась новая система.SPEARandomPAESPESAVEGANPGANSGASPEA2SPEAX0.70.0100.090.230.990.02Random0.76X0.0500.320.0710PAES0.991X0.170.850.9610.49PESA111X0.98110.96VEGA0.9910.290.05X0.8110.3NPGA0.970.980.0700.34X10.1NSGA0.050.270.40.040.910X0SPEA2110.840.160.9411XТаблица 7: Результаты сравнительных тестов (2)В этих двух таблицах часть результатов (те, что близки к 0 или 1) показательны, они дают понять, что один из алгоритмов стабильно лучше другого, остальные же не дают существенной информации, так как являются усредненными.В следующих таблицах приведены результаты сравнения пар алгоритмов с помощью проверки статистических гипотез, так, как было описано в пункт 9.3. Как было сказано, проверялась гипотеза, что результаты одного алгоритма лучше результатов другого по мере С. Соответственно, 1 в клетке означает, что гипотеза для данных двух алгоритмов доказана, 0 — что доказана обратная гипотеза, пустая клетка — что гипотеза не доказана и не опровергнута.Первая таблица для эксперимента с одной системой:SPEARandomPAESPESAVEGANPGANSGASPEA2SPEAX1000010Random0X000010PAES11X01110PESA111X1111VEGA1100X10NPGA11000X10NSGA00000X0SPEA21110111XТаблица 8: Результаты сравнительных тестов: проверка гипотез (1)Вторая таблица для эксперимента с новой системой на каждой итерации:SPEARandomPAESPESAVEGANPGANSGASPEA2SPEAX1000010Random0X000010PAES11X0110PESA111X1111VEGA1100X100NPGA11000X10NSGA00010X0SPEA21110111XТаблица 9: Результаты сравнительных тестов: проверка гипотез (2)ЗаключениеВсе исследуемые алгоритмы прошли первичную проверку, поэтому дальнейшее рассмотрение можно проводить без оглядки на результаты, выдаваемые полным перебором всех вариантов.900 п800♦♦♦700 600 500♦♦♦♦♦ ♦♦♦♦ ♦♦ ♦♦♦ ♦♦♦♦400♦ ♦♦300200100000,05 0,1 0,150,20,25 0,3Рисунок 5 - Алгоритм SPEA на системе из трех узлов (Ось Х— надежность, ось Y - стоимость)Рисунок 6 - Алгоритм SPEAна системе из 20 узлов (Ось Х — надежность, ось Y- стоимость)Для маленьких систем генетический алгоритм не всегда эффективен, тогда как для систем с большим количеством узлов их результаты адекватны и имеют перед результатами прочих алгоритмов то преимущество, что их количество фиксировано.На рисунках 5 и 6 видно, что на маленькой системе в выдаче генетического алгоритма много «мусора», а на системе из большого числа узлов популяция выстраивается в виде приближения множества Парето, причем не сконцентрирована в одной области.Как можно было предположить, метод случайного поиска оказался неэффективен для рассматриваемой задачи. В разделе 4 была приведена иллюстрация, показывающая приблизительный вид множества потенциальных решений; для систем с большим количеством узлов число вариантов с очень низкими показателями надежности и стоимости еще больше. Таким образом, если выбирать каждый раз абсолютно случайный вектор, вероятность попасть в область далекую от Парето-фронта, очень велика. Поэтому направленный поиск в случае данной задачи является необходимостью.Рисунок 7 - Результаты работы генетических алгоритмов (Ось Х — надежность, ось Y- стоимость)Как видно, результаты в целом соответствуют сравнительным таблицам, приведенным в предыдущем подразделе. Результаты достаточно хорошо распределены вдоль Парето-фронта и располагаются от одной из границ до другой. Точность у разных алгоритмов отличается.SPEA2 оказался наиболее эффективным алгоритмом (и визуально по рисунку 7, и по таблицам 8-9 из пункта 9.3), тем самым подтвердилась правильность изменений, внесенных в него по сравнению с SPEA.При применении к рассматриваемой задаче особенно сильно проявился один из отмеченных в обзоре недостатков SPEA— большое количество решений с одинаковым весом. Выше в этом разделе было показано, что Парето-фронт, сгенерированный эвристическими алгоритмами с нефиксированным размером результата, как правило, имеет очень мало точек, которые будут доминировать над практически всей популяцией в SPEA, тем самым уравняв их веса. В SPEA2 же этой проблемы нет.ЗаключениеВ рамках данной работы получены следующие результаты:Изучены и описаны в обзоре методы многокритериальной оптимизации, выдающие в качестве решения Парето-фронт.Среди обозреваемых алгоритмов выбраны и адаптированы для рассматриваемой задачи ряд алгоритмов:PAES, NSGA, NPGA, VEGA, PESA, SPEA, SPEA-2, случайный поиск.Реализованы алгоритмы и программное средство для проведения экспериментов.Проведено экспериментальное исследование выбранных алгоритмовУстановленные важные свойства конкретных алгоритмов:SPEA-2 и PESA — два наиболее эффективных алгоритма для исследуемой задачи.Следом за ними по качеству идут NPGA, VEGA и PAES.Алгоритм SPEA малоэффективен из-за неподходящей к рассматриваемой задаче функции отбора.В качестве дальнейшего развития данной темы можно выделить следующие направления:Изучение влияния начального приближения на результат генетических алгоритмов.Исследование работы алгоритмов при различных настройках.Создание гибридных алгоритмов, комбинирующих свойства описанных в обзоре на разных стадиях работы или изменяющих параметры в процессе работы.Исследование алгоритмов многокритериальной оптимизации, выдающих единственное решение.ЛитератураC.A.Coello A Comprehensive Survey Of Evolutionary-Based Multiobjective Optimization Techniques. Knowledge and Information Systems, vol. 1, no. 3, pp. 269-308, 1999D.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.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.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.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.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 PressH. A. Taboada, FatemaBaheranwala, David W. Coit Practical solutions of multi- objective system reliability design problems using genetic algorithm. (2006).. ReliabilityEngineering & System Safety, 92(3), 314-322N. 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 - 416N. Wattanapongskorn, D.W. Coit Fault-Tolerant embedded system design and optimization considering reliability estimation uncertaint. Reliability Engineering and System Safety, 2007, pp. 395-407.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.М. Мину. Математическое программирование. Теория и алгоритмы.- М.: Наука, 1990.