D-NSGA-II: Dynamic Multi-Objective Optimization Using Modified NSGA-IIΒΆ

The algorithm is implemented based on [3]. D-NSGA-II modifies the commonly-used NSGA-II procedure in tracking a new Pareto-optimal front as soon as there is a change in the problem. The introduction of a few random solutions or a few mutated solutions provides some diversity and gives the algorithm a chance to escape from a local optimum over time.

[1]:
from pymoo.algorithms.moo.dnsga2 import DNSGA2
from pymoo.core.callback import CallbackCollection, Callback
from pymoo.optimize import minimize
from pymoo.problems.dyn import TimeSimulation
from pymoo.problems.dynamic.df import DF1
import matplotlib.pyplot as plt

problem = DF1(taut=2, n_var=2)

algorithm = DNSGA2()

simulation = TimeSimulation()


class ObjectiveSpaceAnimation(Callback):

    def _update(self, algorithm):

        if algorithm.n_gen % 20 == 0:
            F = algorithm.opt.get("F")
            pf = algorithm.problem.pareto_front()

            plt.clf()
            plt.scatter(F[:, 0], F[:, 1])
            if pf is not None:
                plt.plot(pf[:, 0], pf[:, 1], color="black", alpha=0.7)

            plt.show()

res = minimize(problem,
               algorithm,
               termination=('n_gen', 100),
               callback=CallbackCollection(ObjectiveSpaceAnimation(), simulation),
               seed=1,
               verbose=True)

==========================================================================
n_gen  |  n_eval  | n_nds  |      igd      |       gd      |       hv
==========================================================================
     1 |      100 |     22 |  0.0406157738 |  0.0232449442 |  0.3857609533
     2 |      410 |     45 |  0.0263321324 |  0.0207824613 |  0.3960674761
     3 |      620 |     62 |  0.0237748654 |  0.0203548008 |  0.4009007302
     4 |      930 |     58 |  0.0346067981 |  0.0300876898 |  0.3840870050
     5 |     1140 |     88 |  0.0334836462 |  0.0299320209 |  0.3876566424
     6 |     1450 |     57 |  0.0512547245 |  0.0528774022 |  0.3601083284
     7 |     1660 |     84 |  0.0455702841 |  0.0492041654 |  0.3698029876
     8 |     1970 |     50 |  0.0614278344 |  0.0623640078 |  0.3426451356
     9 |     2180 |     68 |  0.0586873395 |  0.0617217600 |  0.3483687313
    10 |     2490 |     56 |  0.0707280473 |  0.0772451610 |  0.3287838862
    11 |     2700 |     65 |  0.0646647058 |  0.0706581281 |  0.3389049648
    12 |     3010 |     48 |  0.0710240693 |  0.0723691723 |  0.3245673141
    13 |     3220 |     71 |  0.0686131431 |  0.0692033978 |  0.3330436708
    14 |     3530 |     61 |  0.0745450091 |  0.0712756130 |  0.3225411355
    15 |     3740 |     85 |  0.0721097194 |  0.0696076243 |  0.3303550918
    16 |     4050 |     82 |  0.0770226806 |  0.0791481651 |  0.3212008750
    17 |     4260 |    100 |  0.0759551977 |  0.0796877644 |  0.3255725897
    18 |     4570 |     79 |  0.0780567829 |  0.0792255693 |  0.3208460392
    19 |     4780 |    100 |  0.0767752831 |  0.0754245937 |  0.3245871718
    20 |     5090 |     93 |  0.0775395030 |  0.0776330687 |  0.3217840824
../../_images/algorithms_moo_dnsga2_3_1.png
    21 |     5300 |    100 |  0.0767647032 |  0.0768481217 |  0.3248824392
    22 |     5610 |    100 |  0.0760216170 |  0.0739669803 |  0.3248936770
    23 |     5820 |    100 |  0.0756579236 |  0.0764579632 |  0.3270964567
    24 |     6130 |    100 |  0.0737687767 |  0.0720297744 |  0.3302190362
    25 |     6340 |    100 |  0.0736659479 |  0.0730912075 |  0.3308874574
    26 |     6650 |    100 |  0.0731545166 |  0.0815881159 |  0.3288540356
    27 |     6860 |    100 |  0.0721427149 |  0.0808767001 |  0.3320348130
    28 |     7170 |     67 |  0.0720931585 |  0.0807877928 |  0.3270910962
    29 |     7380 |     92 |  0.0690956617 |  0.0739976698 |  0.3334097599
    30 |     7690 |     56 |  0.0677577441 |  0.0813987101 |  0.3314955544
    31 |     7900 |     72 |  0.0629420409 |  0.0637868311 |  0.3420432010
    32 |     8210 |     58 |  0.0618027037 |  0.0629233945 |  0.3403101424
    33 |     8420 |     65 |  0.0564889245 |  0.0573917268 |  0.3498165110
    34 |     8730 |     42 |  0.0515244146 |  0.0543256472 |  0.3577657931
    35 |     8940 |     63 |  0.0462319883 |  0.0495466344 |  0.3676830644
    36 |     9250 |     46 |  0.0388020367 |  0.0377727687 |  0.3775898467
    37 |     9460 |     68 |  0.0338576523 |  0.0332735237 |  0.3873106640
    38 |     9770 |     58 |  0.0288631302 |  0.0271924094 |  0.3938744581
    39 |     9980 |     79 |  0.0246669832 |  0.0251419387 |  0.4015148240
    40 |    10290 |     45 |  0.0263042610 |  0.0308257967 |  0.4010065433
../../_images/algorithms_moo_dnsga2_3_3.png
    41 |    10500 |     59 |  0.0182289056 |  0.0210831155 |  0.4122532620
    42 |    10810 |    100 |  0.0149463954 |  0.0142699748 |  0.4560504763
    43 |    11020 |    100 |  0.0148756650 |  0.0148667573 |  0.4580237827
    44 |    11330 |     73 |  0.0282744310 |  0.0271196375 |  0.4730048711
    45 |    11540 |     96 |  0.0299741502 |  0.0285630072 |  0.4785132845
    46 |    11850 |     57 |  0.0442173278 |  0.0419419656 |  0.4963499517
    47 |    12060 |     72 |  0.0484249272 |  0.0485190702 |  0.5041148452
    48 |    12370 |     63 |  0.0623579558 |  0.0659356784 |  0.5254220568
    49 |    12580 |     76 |  0.0675836208 |  0.0628508117 |  0.5346652419
    50 |    12890 |     58 |  0.0862753402 |  0.0816461854 |  0.5579247912
    51 |    13100 |     83 |  0.0902126704 |  0.0871270043 |  0.5667420648
    52 |    13410 |     67 |  0.1052707332 |  0.0994010742 |  0.5909723459
    53 |    13620 |     99 |  0.1075585802 |  0.1019567776 |  0.5959646038
    54 |    13930 |     86 |  0.1203967122 |  0.1181201594 |  0.6155533874
    55 |    14140 |    100 |  0.1232812380 |  0.1252262959 |  0.6213457202
    56 |    14450 |     88 |  0.1333269434 |  0.1358633262 |  0.6374913733
    57 |    14660 |    100 |  0.1350379099 |  0.1358659370 |  0.6402714617
    58 |    14970 |     92 |  0.1411733326 |  0.1517724007 |  0.6495374473
    59 |    15180 |    100 |  0.1438606029 |  0.1479847764 |  0.6533479913
    60 |    15490 |     98 |  0.1462196018 |  0.1598204955 |  0.6567650077
../../_images/algorithms_moo_dnsga2_3_5.png
    61 |    15700 |    100 |  0.1478347821 |  0.1579384036 |  0.6584202651
    62 |    16010 |    100 |  0.1460618809 |  0.1543043303 |  0.6551322642
    63 |    16220 |    100 |  0.1461939278 |  0.1585676058 |  0.6552147488
    64 |    16530 |    100 |  0.1400418007 |  0.1454001131 |  0.6437867692
    65 |    16740 |    100 |  0.1400851819 |  0.1420272960 |  0.6442184088
    66 |    17050 |    100 |  0.1259024551 |  0.1289662197 |  0.6229861641
    67 |    17260 |    100 |  0.1262934239 |  0.1288227002 |  0.6239578263
    68 |    17570 |     97 |  0.1044057675 |  0.1065120638 |  0.5924824716
    69 |    17780 |    100 |  0.1071659543 |  0.1119953635 |  0.5966936868
    70 |    18090 |     74 |  0.0837471664 |  0.0874156951 |  0.5611377539
    71 |    18300 |    100 |  0.0856398376 |  0.0897192729 |  0.5661534032
    72 |    18610 |     62 |  0.0624133301 |  0.0618096331 |  0.5277147639
    73 |    18820 |     80 |  0.0662584736 |  0.0687729684 |  0.5329110043
    74 |    19130 |     60 |  0.0487452657 |  0.0630417924 |  0.5003246007
    75 |    19340 |     88 |  0.0481605727 |  0.0593538161 |  0.5077002330
    76 |    19650 |     54 |  0.0270897006 |  0.0321536868 |  0.4651321439
    77 |    19860 |     74 |  0.0282078117 |  0.0340163609 |  0.4743821213
    78 |    20170 |     42 |  0.0196510050 |  0.0149372843 |  0.4356000388
    79 |    20380 |     62 |  0.0150939295 |  0.0122741334 |  0.4460344548
    80 |    20690 |     41 |  0.0193800204 |  0.0119109358 |  0.4132807114
../../_images/algorithms_moo_dnsga2_3_7.png
    81 |    20900 |     61 |  0.0137014765 |  0.0097048739 |  0.4224286253
    82 |    21210 |     91 |  0.0202126466 |  0.0192038970 |  0.4088260759
    83 |    21420 |    100 |  0.0187103851 |  0.0187444030 |  0.4121792354
    84 |    21730 |     60 |  0.0404702340 |  0.0454094217 |  0.3757471126
    85 |    21940 |     71 |  0.0354560658 |  0.0358390005 |  0.3834515498
    86 |    22250 |     51 |  0.0529138094 |  0.0533157448 |  0.3545642949
    87 |    22460 |     60 |  0.0497058101 |  0.0494229431 |  0.3619749759
    88 |    22770 |     54 |  0.0593052089 |  0.0589529084 |  0.3451109034
    89 |    22980 |     81 |  0.0567458089 |  0.0552530226 |  0.3504790478
    90 |    23290 |     60 |  0.0645442407 |  0.0672821037 |  0.3384956450
    91 |    23500 |     81 |  0.0616334824 |  0.0619673684 |  0.3450492851
    92 |    23810 |     50 |  0.0697778769 |  0.0766854153 |  0.3301403594
    93 |    24020 |     79 |  0.0670055508 |  0.0695406200 |  0.3360101771
    94 |    24330 |     69 |  0.0759941881 |  0.0759065545 |  0.3212419929
    95 |    24540 |     84 |  0.0730221588 |  0.0782523446 |  0.3284115028
    96 |    24850 |     62 |  0.0794457311 |  0.0855982456 |  0.3172744673
    97 |    25060 |     88 |  0.0767291898 |  0.0837423684 |  0.3221836726
    98 |    25370 |     78 |  0.0799834732 |  0.0868988771 |  0.3164850150
    99 |    25580 |    100 |  0.0777148831 |  0.0824918900 |  0.3223695802
   100 |    25890 |     74 |  0.0784573875 |  0.0796731981 |  0.3200140153
../../_images/algorithms_moo_dnsga2_3_9.png