nsga2_fresh_acc.py

import numpy as np
import copy
import random
import matplotlib.pyplot as plt
from Power_Failure import Power_Failure
from Graph import Power_Graph
from pypower.case118 import case118
from pypower.case300 import case300
from pypower.case500 import case500
from pypower.case2383 import case2383
from pypower.rundcpf import rundcpf
from time import clock
import heapq
from Attack import Attack
from individual import individual
from time import sleep
from ga import GA
import sys


class nsga2(object):
    """docstring for nsga2"""

    def __init__(self, size, attack_num, crossover_num, iters, population_list_num):
        super(nsga2, self).__init__()
        self.size = size
        self.attack_num = attack_num
        self.crossover_num = crossover_num
        self.iters = iters
        self.population_list_num = population_list_num

    def begin(self):
        init_list = []
        for i in range(self.size):
            init_list.append(i + 1)

        init_population_list = []

        for i in range(self.population_list_num):
            attack_list = random.sample(init_list, self.attack_num)
            single_popu_list = individual(0, 0, [], 0, 0, 0, attack_list)
            init_population_list.append(copy.deepcopy(single_popu_list))

            # 计算rp和sn
            a1, a2, a3, a4, a5 = self.attack_with_cal(init_population_list[i].attack_list)
            self.f1 = a2
            self.f2 = a4

        self.fast_non_dominated_sort(init_population_list)

        pc = 0.5
        pm = 0.8
        return init_population_list, pc, pm



    def begin2(self, var):
        if self.size == 300:
            degree_list = [268, 109, 31, 190, 3, 64, 105, 116, 119, 15, 35, 112, 177, 210, 270, 7, 11, 36, 38, 54, 61,
                           79, 81, 83, 122, 124, 189, 198, 216, 2, 12, 19, 20, 22, 23, 27, 29, 32, 37, 39, 43, 48, 49,
                           59, 60, 62, 66, 68, 71, 86, 89, 90, 97, 98, 99, 101, 106, 125, 152, 154, 157, 167, 175, 196,
                           199, 213, 224, 226, 266, 269, 272, 1, 5, 8, 16, 18, 25, 34, 40, 41, 42, 44, 47, 53, 55, 57,
                           63, 65, 72, 73, 74, 75, 76, 77, 78, 82, 84, 85, 87, 88, 93, 100, 102, 103, 104, 107, 108,
                           111, 113, 115, 118, 120, 121, 127, 132, 134, 136, 137, 138, 143, 147, 148, 151, 153, 155,
                           158, 160, 168, 169, 172, 173, 174, 176, 179, 183, 184, 185, 187, 191, 193, 194, 197, 203,
                           204, 207, 208, 217, 221, 225, 227, 267, 271, 273, 274, 276, 4, 6, 9, 10, 13, 14, 17, 21, 24,
                           26, 28, 30, 33, 45, 46, 50, 51, 52, 56, 58, 67, 70, 80, 91, 92, 94, 95, 96, 110, 114, 117,
                           123, 126, 128, 129, 130, 131, 133, 135, 139, 140, 141, 142, 144, 145, 146, 149, 156, 159,
                           161, 162, 163, 165, 166, 170, 171, 178, 180, 181, 182, 186, 188, 195, 200, 202, 205, 211,
                           214, 219, 222, 223, 228, 245, 246, 291, 294, 69, 150, 164, 192, 201, 206, 209, 212, 215, 218,
                           220, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 247,
                           248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265,
                           275, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 292, 293, 295,
                           296, 297, 298, 299, 300]
            load_list = [117, 171, 99, 150, 19, 118, 213, 17, 206, 100, 104, 170, 149, 211, 202, 157, 204, 212, 119,
                         106, 5, 201, 146, 199, 103, 116, 214, 217, 161, 101, 53, 61, 207, 51, 63, 134, 38, 167, 154,
                         195, 203, 200, 114, 152, 14, 210, 32, 10, 236, 120, 163, 197, 15, 136, 6, 59, 231, 88, 243,
                         196, 49, 9, 190, 208, 43, 1, 122, 35, 31, 141, 81, 11, 21, 102, 83, 20, 225, 135, 64, 158, 160,
                         183, 55, 133, 159, 26, 46, 80, 75, 177, 8, 90, 127, 45, 224, 226, 78, 165, 166, 13, 41, 105,
                         60, 121, 2, 58, 115, 27, 240, 86, 66, 194, 34, 24, 74, 176, 182, 42, 180, 162, 79, 37, 181,
                         188, 69, 292, 140, 178, 138, 84, 89, 293, 241, 227, 228, 237, 25, 67, 156, 179, 151, 294, 92,
                         235, 124, 48, 193, 22, 3, 91, 93, 76, 131, 77, 97, 50, 238, 185, 47, 175, 85, 222, 168, 187,
                         155, 274, 87, 267, 299, 285, 268, 287, 232, 233, 282, 286, 280, 284, 290, 283, 275, 281, 277,
                         300, 297, 298, 288, 269, 289, 278, 279, 4, 7, 12, 16, 18, 23, 28, 29, 30, 33, 36, 39, 40, 52,
                         54, 56, 57, 62, 65, 68, 70, 71, 72, 73, 82, 94, 95, 96, 98, 107, 108, 109, 110, 111, 112, 113,
                         123, 125, 126, 128, 129, 130, 132, 137, 139, 142, 143, 144, 145, 147, 148, 153, 164, 169, 172,
                         173, 174, 184, 189, 191, 192, 198, 205, 209, 215, 216, 218, 219, 220, 221, 223, 245, 246, 247,
                         248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266,
                         270, 271, 272, 273, 276, 291, 295, 296, 44, 239, 234, 186, 229, 230, 244, 242]

        elif self.size == 118:
            degree_list = [49, 100, 12, 80, 17, 37, 59, 69, 77, 92, 5, 15, 32, 54, 56, 70, 75, 85, 94, 96, 105, 11, 19,
                           23, 27, 30, 34, 40, 61, 62, 65, 66, 68, 89, 103, 110, 3, 8, 24, 25, 31, 38, 42, 45, 46, 47,
                           51, 55, 60, 64, 71, 82, 83, 104, 106, 1, 2, 4, 6, 7, 9, 13, 14, 16, 18, 20, 21, 22, 26, 28,
                           29, 33, 35, 36, 39, 41, 43, 44, 48, 50, 52, 53, 57, 58, 63, 67, 72, 74, 76, 78, 79, 81, 84,
                           86, 88, 90, 91, 93, 95, 97, 98, 99, 101, 102, 107, 108, 109, 113, 114, 115, 118, 10, 73, 87,
                           111, 112, 116, 117]
            load_list = [59, 116, 90, 80, 54, 42, 15, 49, 56, 60, 62, 27, 78, 11, 74, 76, 112, 40, 70, 92, 55, 77, 18,
                         32, 34, 82, 45, 6, 1, 107, 88, 12, 75, 19, 31, 106, 95, 99, 3, 4, 66, 79, 110, 96, 104, 41,
                         100, 13, 47, 98, 35, 118, 36, 105, 94, 8, 46, 67, 39, 16, 29, 85, 33, 53, 103, 101, 115, 86, 2,
                         48, 83, 117, 7, 20, 43, 52, 28, 50, 51, 44, 97, 14, 21, 24, 57, 58, 72, 93, 17, 84, 22, 91,
                         109, 114, 23, 73, 113, 102, 108, 5, 9, 10, 25, 26, 30, 37, 38, 61, 63, 64, 65, 68, 69, 71, 81,
                         87, 89, 111]


        elif self.size == 500:
            degree_list = [386, 428, 253, 112, 407, 191, 220, 287, 417, 31, 123, 143, 246, 276, 360, 399, 440, 479, 15,
                           48, 165, 195, 232, 263, 300, 349, 376, 387, 426, 471, 14, 23, 24, 62, 70, 133, 162, 176, 205,
                           233, 236, 262, 272, 295, 304, 312, 333, 336, 369, 429, 454, 457, 468, 496, 7, 12, 19, 58, 66,
                           68, 80, 87, 99, 114, 129, 131, 149, 166, 172, 179, 202, 212, 221, 228, 281, 297, 308, 318,
                           322, 332, 342, 358, 367, 449, 453, 1, 3, 5, 8, 10, 21, 27, 29, 33, 35, 37, 39, 40, 42, 44,
                           46, 53, 55, 57, 60, 65, 74, 76, 78, 81, 83, 85, 89, 91, 93, 95, 97, 102, 104, 106, 108, 110,
                           117, 119, 121, 124, 135, 137, 139, 141, 146, 147, 151, 152, 154, 156, 158, 160, 163, 170,
                           181, 183, 185, 187, 189, 193, 196, 200, 208, 210, 214, 216, 218, 226, 230, 235, 238, 240,
                           242, 244, 251, 260, 267, 269, 274, 279, 283, 285, 289, 291, 293, 298, 310, 314, 316, 320,
                           324, 326, 328, 330, 338, 340, 345, 347, 354, 356, 365, 371, 372, 374, 378, 380, 382, 384,
                           401, 403, 405, 408, 415, 419, 421, 423, 441, 445, 447, 462, 464, 465, 467, 472, 476, 485,
                           488, 491, 493, 495, 500, 175, 247, 271, 425, 452, 459, 460, 461, 466, 469, 470, 473, 474,
                           475, 477, 478, 486, 487, 489, 490, 492, 499, 2, 4, 6, 9, 11, 13, 16, 17, 18, 20, 22, 25, 26,
                           28, 30, 32, 34, 36, 38, 41, 43, 45, 47, 49, 50, 51, 52, 54, 56, 59, 61, 63, 64, 67, 69, 71,
                           72, 73, 75, 77, 79, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 101, 103, 105, 107, 109, 111,
                           113, 115, 116, 118, 120, 122, 125, 126, 127, 128, 130, 132, 134, 136, 138, 140, 142, 144,
                           145, 148, 150, 153, 155, 157, 159, 161, 164, 167, 168, 169, 171, 173, 174, 177, 178, 180,
                           182, 184, 186, 188, 190, 192, 194, 197, 198, 199, 201, 203, 204, 206, 207, 209, 211, 213,
                           215, 217, 219, 222, 223, 224, 225, 227, 229, 231, 234, 237, 239, 241, 243, 245, 248, 249,
                           250, 252, 254, 255, 256, 257, 258, 259, 261, 264, 265, 266, 268, 270, 273, 275, 277, 278,
                           280, 282, 284, 286, 288, 290, 292, 294, 296, 299, 301, 302, 303, 305, 306, 307, 309, 311,
                           313, 315, 317, 319, 321, 323, 325, 327, 329, 331, 334, 335, 337, 339, 341, 343, 344, 346,
                           348, 350, 351, 352, 353, 355, 357, 359, 361, 362, 363, 364, 366, 368, 370, 373, 375, 377,
                           379, 381, 383, 385, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 400, 402, 404,
                           406, 409, 410, 411, 412, 413, 414, 416, 418, 420, 422, 424, 427, 430, 431, 432, 433, 434,
                           435, 436, 437, 438, 439, 442, 443, 444, 446, 448, 450, 451, 455, 456, 458, 463, 480, 481,
                           482, 483, 484, 494, 497, 498]
            load_list = [474, 142, 424, 321, 22, 59, 4, 469, 499, 327, 491, 252, 282, 268, 157, 325, 130, 30, 164, 488,
                         213, 153, 461, 377, 446, 402, 303, 348, 199, 215, 182, 209, 105, 138, 307, 495, 339, 243, 459,
                         486, 155, 92, 418, 28, 111, 266, 84, 234, 476, 492, 288, 41, 448, 148, 331, 366, 357, 217, 229,
                         122, 472, 422, 109, 346, 113, 204, 186, 323, 311, 47, 36, 466, 2, 134, 470, 397, 239, 103, 13,
                         98, 385, 370, 54, 64, 211, 96, 284, 120, 477, 364, 184, 383, 490, 373, 194, 485, 136, 460, 329,
                         161, 294, 132, 34, 375, 341, 500, 52, 400, 159, 207, 26, 355, 404, 241, 261, 86, 69, 280, 398,
                         192, 107, 359, 299, 427, 180, 190, 100, 379, 465, 313, 171, 245, 487, 368, 452, 188, 381, 32,
                         273, 478, 309, 201, 118, 177, 286, 259, 296, 292, 174, 77, 178, 270, 416, 90, 278, 337, 227,
                         75, 88, 406, 420, 94, 115, 203, 67, 20, 43, 493, 468, 317, 290, 489, 6, 173, 116, 206, 237,
                         343, 11, 344, 25, 56, 451, 45, 150, 450, 473, 101, 335, 467, 334, 315, 277, 79, 51, 219, 140,
                         61, 475, 38, 1, 3, 5, 7, 8, 9, 10, 12, 14, 15, 16, 17, 18, 19, 21, 23, 24, 27, 29, 31, 33, 35,
                         37, 39, 40, 42, 44, 46, 48, 49, 50, 53, 55, 57, 58, 60, 62, 63, 65, 66, 68, 70, 71, 72, 73, 74,
                         76, 78, 80, 81, 82, 83, 85, 87, 89, 91, 93, 95, 97, 99, 102, 104, 106, 108, 110, 112, 114, 117,
                         119, 121, 123, 124, 125, 126, 127, 128, 129, 131, 133, 135, 137, 139, 141, 143, 144, 145, 146,
                         147, 149, 151, 152, 154, 156, 158, 160, 162, 163, 165, 166, 167, 168, 169, 170, 172, 175, 176,
                         179, 181, 183, 185, 187, 189, 191, 193, 195, 196, 197, 198, 200, 202, 205, 208, 210, 212, 214,
                         216, 218, 220, 221, 222, 223, 224, 225, 226, 228, 230, 231, 232, 233, 235, 236, 238, 240, 242,
                         244, 246, 247, 248, 249, 250, 251, 253, 254, 255, 256, 257, 258, 260, 262, 263, 264, 265, 267,
                         269, 271, 272, 274, 275, 276, 279, 281, 283, 285, 287, 289, 291, 293, 295, 297, 298, 300, 301,
                         302, 304, 305, 306, 308, 310, 312, 314, 316, 318, 319, 320, 322, 324, 326, 328, 330, 332, 333,
                         336, 338, 340, 342, 345, 347, 349, 350, 351, 352, 353, 354, 356, 358, 360, 361, 362, 363, 365,
                         367, 369, 371, 372, 374, 376, 378, 380, 382, 384, 386, 387, 388, 389, 390, 391, 392, 393, 394,
                         395, 396, 399, 401, 403, 405, 407, 408, 409, 410, 411, 412, 413, 414, 415, 417, 419, 421, 423,
                         425, 426, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444,
                         445, 447, 449, 453, 454, 455, 456, 457, 458, 462, 463, 464, 471, 479, 480, 481, 482, 483, 484,
                         494, 496, 497, 498]

        # print(len(degree_list),len(load_list))

        elif self.size == 2383:
            degree_list = [7, 1095, 1426, 1647, 1919, 1920, 18, 322, 425, 644, 978, 1096, 1217, 1502, 1552, 1906, 2113,
                           4, 29, 123, 321, 526, 540, 645, 778, 796, 821, 912, 979, 997, 1138, 1216, 1489, 1524, 1553,
                           1748, 1814, 1987, 2166, 2170, 2196, 2339, 6, 11, 124, 131, 132, 140, 245, 353, 546, 568, 613,
                           679, 703, 716, 717, 727, 750, 797, 822, 834, 995, 1183, 1184, 1190, 1192, 1213, 1233, 1244,
                           1250, 1343, 1483, 1503, 1538, 1539, 1649, 1650, 1680, 1747, 1760, 1761, 1880, 1881, 1882,
                           1883, 2112, 2165, 2169, 2195, 2260, 2261, 2323, 2357, 2380, 10, 16, 17, 50, 63, 64, 67, 71,
                           74, 80, 103, 111, 125, 130, 135, 138, 143, 144, 147, 151, 166, 176, 213, 246, 310, 332, 352,
                           354, 365, 366, 374, 477, 493, 494, 539, 545, 569, 615, 650, 663, 678, 689, 707, 726, 755,
                           858, 859, 870, 966, 967, 996, 1114, 1120, 1140, 1141, 1182, 1201, 1293, 1382, 1383, 1384,
                           1416, 1418, 1431, 1469, 1504, 1514, 1536, 1556, 1623, 1624, 1681, 1686, 1822, 1823, 1839,
                           1845, 1846, 1865, 1884, 1885, 1907, 2010, 2090, 2119, 2134, 2157, 2159, 2167, 2186, 2187,
                           2257, 2258, 2273, 2377, 5, 12, 13, 14, 15, 20, 22, 23, 25, 27, 41, 42, 47, 48, 49, 60, 61,
                           68, 69, 73, 76, 77, 81, 82, 83, 84, 85, 86, 87, 92, 93, 94, 96, 100, 101, 104, 106, 107, 113,
                           118, 120, 121, 126, 133, 139, 141, 142, 145, 148, 150, 152, 154, 159, 160, 163, 165, 167,
                           174, 179, 192, 194, 211, 219, 240, 294, 305, 309, 342, 346, 347, 355, 359, 361, 411, 502,
                           514, 515, 525, 527, 551, 552, 564, 565, 612, 617, 655, 688, 694, 706, 712, 740, 754, 798,
                           799, 836, 871, 892, 911, 915, 916, 919, 920, 944, 968, 973, 1024, 1025, 1050, 1053, 1054,
                           1087, 1097, 1098, 1106, 1115, 1139, 1203, 1212, 1230, 1245, 1251, 1284, 1328, 1345, 1346,
                           1356, 1375, 1415, 1427, 1430, 1432, 1435, 1452, 1470, 1476, 1505, 1517, 1523, 1540, 1565,
                           1576, 1577, 1580, 1581, 1603, 1618, 1619, 1637, 1658, 1664, 1669, 1673, 1674, 1687, 1712,
                           1717, 1734, 1796, 1840, 1873, 1877, 1878, 1902, 1903, 1914, 1921, 1922, 1945, 1963, 1988,
                           2021, 2037, 2038, 2091, 2121, 2124, 2137, 2138, 2168, 2172, 2173, 2188, 2191, 2218, 2221,
                           2237, 2274, 2313, 2324, 2342, 2361, 2362, 2378, 2381, 3, 19, 28, 30, 31, 32, 34, 35, 36, 37,
                           38, 39, 40, 43, 44, 45, 46, 51, 53, 54, 55, 59, 62, 66, 75, 78, 88, 89, 90, 91, 95, 98, 99,
                           102, 105, 108, 114, 115, 116, 117, 127, 129, 134, 157, 158, 161, 162, 164, 170, 171, 172,
                           173, 175, 178, 202, 214, 220, 255, 265, 277, 281, 282, 283, 286, 295, 299, 300, 312, 336,
                           337, 344, 360, 367, 368, 373, 375, 380, 413, 445, 446, 447, 448, 455, 456, 464, 476, 481,
                           482, 489, 490, 511, 512, 516, 517, 518, 519, 542, 543, 547, 549, 556, 557, 573, 581, 582,
                           588, 619, 628, 633, 634, 635, 639, 641, 643, 653, 662, 665, 667, 670, 680, 685, 690, 696,
                           709, 710, 711, 737, 744, 763, 770, 771, 785, 807, 812, 815, 817, 819, 825, 826, 829, 833,
                           840, 851, 855, 856, 864, 869, 874, 876, 878, 879, 885, 893, 898, 903, 905, 906, 921, 923,
                           926, 928, 929, 932, 936, 938, 953, 961, 971, 972, 981, 985, 986, 989, 990, 994, 1003, 1007,
                           1008, 1017, 1018, 1019, 1020, 1043, 1044, 1049, 1057, 1059, 1063, 1065, 1066, 1069, 1070,
                           1081, 1082, 1083, 1088, 1092, 1093, 1101, 1107, 1108, 1111, 1112, 1119, 1122, 1127, 1129,
                           1131, 1133, 1149, 1151, 1153, 1158, 1161, 1162, 1166, 1167, 1178, 1188, 1189, 1191, 1193,
                           1199, 1200, 1202, 1209, 1219, 1222, 1226, 1227, 1231, 1232, 1239, 1243, 1248, 1256, 1257,
                           1261, 1265, 1271, 1274, 1275, 1285, 1288, 1294, 1298, 1306, 1307, 1311, 1315, 1318, 1319,
                           1323, 1329, 1334, 1335, 1344, 1353, 1362, 1365, 1371, 1376, 1378, 1389, 1390, 1392, 1397,
                           1401, 1407, 1413, 1417, 1439, 1440, 1443, 1448, 1449, 1453, 1459, 1460, 1482, 1484, 1490,
                           1491, 1494, 1498, 1499, 1511, 1513, 1518, 1520, 1522, 1531, 1532, 1537, 1548, 1560, 1569,
                           1570, 1574, 1589, 1592, 1602, 1609, 1610, 1617, 1620, 1635, 1638, 1655, 1656, 1662, 1667,
                           1684, 1694, 1726, 1737, 1739, 1743, 1744, 1776, 1802, 1810, 1830, 1889, 1898, 1900, 1901,
                           1918, 1925, 1926, 1956, 1957, 1981, 1986, 2006, 2007, 2015, 2018, 2022, 2044, 2045, 2047,
                           2056, 2059, 2060, 2061, 2064, 2065, 2066, 2067, 2068, 2069, 2070, 2071, 2072, 2073, 2074,
                           2076, 2077, 2078, 2079, 2080, 2085, 2087, 2108, 2139, 2158, 2203, 2209, 2224, 2229, 2232,
                           2233, 2235, 2244, 2245, 2249, 2251, 2272, 2300, 2310, 2316, 2328, 2338, 2340, 2343, 2352,
                           2365, 2366, 2367, 2374, 2379, 1, 2, 8, 9, 21, 24, 26, 33, 52, 56, 65, 70, 79, 112, 128, 149,
                           155, 156, 168, 169, 177, 182, 183, 184, 186, 187, 188, 189, 190, 191, 193, 195, 198, 199,
                           200, 201, 203, 206, 207, 208, 209, 210, 212, 215, 216, 217, 218, 221, 222, 223, 224, 225,
                           226, 227, 228, 229, 230, 233, 234, 235, 236, 237, 238, 239, 241, 242, 243, 244, 247, 248,
                           249, 250, 253, 254, 256, 257, 258, 259, 260, 261, 262, 263, 264, 266, 267, 269, 272, 273,
                           274, 275, 278, 279, 280, 284, 285, 287, 288, 289, 290, 291, 293, 296, 297, 298, 303, 304,
                           306, 307, 308, 311, 314, 315, 316, 317, 318, 319, 320, 323, 324, 325, 326, 333, 334, 335,
                           338, 339, 340, 341, 343, 345, 348, 349, 350, 351, 356, 357, 363, 364, 369, 370, 371, 372,
                           376, 377, 378, 379, 381, 384, 385, 386, 387, 388, 389, 392, 393, 394, 395, 396, 401, 404,
                           405, 406, 407, 408, 409, 410, 412, 415, 416, 417, 420, 423, 424, 426, 427, 428, 429, 430,
                           431, 432, 433, 434, 437, 438, 439, 440, 441, 442, 443, 444, 451, 452, 457, 458, 459, 460,
                           461, 462, 463, 465, 467, 468, 471, 472, 473, 474, 475, 478, 483, 484, 485, 486, 487, 488,
                           491, 492, 497, 500, 501, 503, 504, 505, 506, 507, 508, 509, 510, 520, 523, 524, 528, 529,
                           530, 531, 532, 533, 534, 535, 536, 537, 538, 544, 548, 550, 553, 554, 555, 558, 559, 560,
                           563, 566, 567, 570, 571, 572, 575, 576, 577, 578, 579, 583, 584, 585, 586, 587, 589, 590,
                           591, 592, 593, 594, 595, 596, 598, 600, 601, 602, 603, 604, 605, 606, 607, 609, 610, 611,
                           614, 616, 618, 620, 621, 622, 623, 624, 625, 626, 627, 629, 630, 631, 632, 636, 637, 638,
                           640, 642, 646, 647, 648, 649, 651, 652, 654, 656, 657, 658, 660, 661, 664, 666, 668, 669,
                           671, 672, 674, 675, 676, 677, 682, 683, 684, 686, 687, 691, 692, 693, 695, 697, 698, 699,
                           700, 701, 702, 704, 705, 708, 713, 714, 715, 718, 719, 720, 721, 722, 723, 724, 725, 728,
                           729, 730, 731, 732, 733, 734, 735, 736, 738, 739, 741, 742, 743, 745, 746, 747, 748, 749,
                           751, 752, 753, 756, 757, 758, 759, 760, 762, 764, 765, 766, 768, 769, 772, 773, 774, 775,
                           776, 777, 779, 780, 781, 782, 783, 784, 792, 794, 795, 802, 804, 808, 809, 813, 814, 820,
                           827, 830, 835, 837, 838, 839, 849, 850, 852, 857, 860, 861, 862, 865, 866, 872, 877, 882,
                           883, 886, 887, 888, 889, 890, 891, 894, 895, 896, 899, 900, 901, 904, 908, 909, 910, 913,
                           914, 917, 918, 924, 939, 942, 943, 947, 948, 949, 954, 957, 959, 962, 963, 964, 965, 974,
                           975, 982, 991, 992, 993, 998, 999, 1004, 1011, 1012, 1021, 1026, 1030, 1031, 1039, 1040,
                           1045, 1051, 1052, 1055, 1058, 1071, 1074, 1075, 1076, 1077, 1078, 1079, 1084, 1086, 1089,
                           1094, 1099, 1102, 1103, 1104, 1105, 1113, 1117, 1121, 1123, 1132, 1136, 1142, 1143, 1144,
                           1145, 1146, 1147, 1148, 1154, 1155, 1156, 1163, 1168, 1169, 1170, 1171, 1175, 1179, 1181,
                           1185, 1194, 1195, 1196, 1204, 1205, 1206, 1207, 1214, 1215, 1220, 1223, 1228, 1229, 1234,
                           1235, 1236, 1237, 1240, 1241, 1249, 1253, 1259, 1260, 1262, 1266, 1267, 1268, 1269, 1276,
                           1277, 1278, 1279, 1282, 1283, 1289, 1290, 1291, 1292, 1295, 1301, 1303, 1308, 1309, 1310,
                           1312, 1313, 1320, 1325, 1326, 1330, 1331, 1336, 1337, 1338, 1339, 1342, 1347, 1348, 1351,
                           1354, 1355, 1357, 1358, 1359, 1360, 1363, 1366, 1367, 1368, 1369, 1372, 1373, 1374, 1379,
                           1380, 1381, 1385, 1388, 1393, 1394, 1398, 1399, 1402, 1403, 1408, 1410, 1411, 1414, 1419,
                           1420, 1421, 1422, 1423, 1424, 1425, 1436, 1444, 1445, 1450, 1451, 1454, 1461, 1462, 1463,
                           1467, 1468, 1475, 1477, 1478, 1479, 1485, 1486, 1487, 1488, 1492, 1495, 1500, 1501, 1506,
                           1507, 1508, 1512, 1515, 1525, 1526, 1527, 1528, 1533, 1534, 1535, 1543, 1544, 1545, 1546,
                           1549, 1557, 1561, 1562, 1563, 1564, 1566, 1571, 1572, 1573, 1575, 1578, 1579, 1582, 1583,
                           1584, 1585, 1586, 1587, 1593, 1594, 1595, 1598, 1599, 1600, 1601, 1605, 1606, 1607, 1608,
                           1612, 1613, 1616, 1622, 1625, 1628, 1629, 1632, 1633, 1634, 1639, 1640, 1641, 1642, 1643,
                           1644, 1645, 1646, 1651, 1652, 1653, 1654, 1657, 1659, 1660, 1661, 1663, 1666, 1668, 1675,
                           1676, 1679, 1682, 1683, 1688, 1689, 1690, 1691, 1693, 1697, 1700, 1701, 1702, 1703, 1704,
                           1705, 1709, 1715, 1716, 1719, 1720, 1723, 1724, 1727, 1728, 1729, 1730, 1731, 1733, 1735,
                           1736, 1742, 1745, 1746, 1752, 1753, 1755, 1756, 1757, 1758, 1759, 1762, 1763, 1764, 1766,
                           1767, 1772, 1773, 1775, 1777, 1778, 1781, 1782, 1783, 1784, 1786, 1787, 1788, 1789, 1790,
                           1791, 1793, 1794, 1795, 1797, 1801, 1804, 1807, 1809, 1812, 1818, 1819, 1820, 1824, 1825,
                           1826, 1827, 1828, 1829, 1831, 1832, 1833, 1834, 1835, 1836, 1837, 1838, 1843, 1844, 1847,
                           1848, 1850, 1853, 1854, 1855, 1856, 1859, 1860, 1861, 1862, 1863, 1864, 1867, 1868, 1869,
                           1871, 1874, 1875, 1876, 1886, 1888, 1891, 1892, 1893, 1894, 1895, 1897, 1904, 1910, 1911,
                           1912, 1913, 1916, 1917, 1923, 1924, 1927, 1929, 1930, 1931, 1932, 1933, 1934, 1935, 1939,
                           1942, 1943, 1944, 1946, 1947, 1948, 1949, 1950, 1951, 1952, 1953, 1955, 1959, 1960, 1962,
                           1964, 1965, 1966, 1967, 1968, 1969, 1970, 1971, 1974, 1975, 1976, 1977, 1978, 1983, 1984,
                           1985, 1989, 1990, 1991, 1992, 1993, 1995, 1996, 1998, 1999, 2000, 2001, 2002, 2011, 2012,
                           2013, 2014, 2020, 2023, 2025, 2027, 2029, 2032, 2033, 2034, 2035, 2036, 2041, 2042, 2043,
                           2046, 2048, 2049, 2050, 2052, 2054, 2055, 2058, 2075, 2084, 2086, 2088, 2089, 2092, 2093,
                           2095, 2096, 2097, 2098, 2099, 2100, 2101, 2102, 2103, 2104, 2105, 2106, 2107, 2114, 2116,
                           2117, 2118, 2120, 2122, 2123, 2125, 2126, 2127, 2129, 2131, 2132, 2133, 2135, 2136, 2140,
                           2141, 2142, 2143, 2145, 2146, 2147, 2150, 2151, 2152, 2154, 2155, 2156, 2160, 2161, 2164,
                           2171, 2174, 2175, 2177, 2178, 2179, 2180, 2184, 2185, 2190, 2192, 2193, 2194, 2197, 2198,
                           2199, 2200, 2202, 2204, 2205, 2206, 2208, 2210, 2211, 2212, 2213, 2214, 2215, 2216, 2217,
                           2220, 2222, 2223, 2225, 2226, 2227, 2228, 2230, 2231, 2234, 2236, 2238, 2239, 2240, 2241,
                           2242, 2243, 2246, 2247, 2248, 2250, 2254, 2255, 2256, 2262, 2263, 2264, 2265, 2267, 2268,
                           2269, 2270, 2271, 2275, 2276, 2278, 2279, 2280, 2281, 2282, 2283, 2284, 2285, 2286, 2287,
                           2288, 2290, 2292, 2293, 2294, 2295, 2296, 2298, 2299, 2303, 2304, 2305, 2306, 2308, 2309,
                           2311, 2317, 2318, 2319, 2321, 2322, 2326, 2327, 2329, 2330, 2331, 2332, 2333, 2334, 2335,
                           2336, 2341, 2344, 2345, 2348, 2350, 2351, 2353, 2354, 2355, 2356, 2358, 2359, 2360, 2363,
                           2368, 2372, 2375, 2376, 2382, 2383, 57, 58, 72, 97, 109, 110, 119, 122, 136, 137, 146, 153,
                           180, 181, 185, 196, 197, 204, 205, 231, 232, 251, 252, 268, 270, 271, 276, 292, 301, 302,
                           313, 327, 328, 329, 330, 331, 358, 362, 382, 383, 390, 391, 397, 398, 399, 400, 402, 403,
                           414, 418, 419, 421, 422, 435, 436, 449, 450, 453, 454, 466, 469, 470, 479, 480, 495, 496,
                           498, 499, 513, 521, 522, 541, 561, 562, 574, 580, 597, 599, 608, 659, 673, 681, 761, 767,
                           786, 787, 788, 789, 790, 791, 793, 800, 801, 803, 805, 806, 810, 811, 816, 818, 823, 824,
                           828, 831, 832, 841, 842, 843, 844, 845, 846, 847, 848, 853, 854, 863, 867, 868, 873, 875,
                           880, 881, 884, 897, 902, 907, 922, 925, 927, 930, 931, 933, 934, 935, 937, 940, 941, 945,
                           946, 950, 951, 952, 955, 956, 958, 960, 969, 970, 976, 977, 980, 983, 984, 987, 988, 1000,
                           1001, 1002, 1005, 1006, 1009, 1010, 1013, 1014, 1015, 1016, 1022, 1023, 1027, 1028, 1029,
                           1032, 1033, 1034, 1035, 1036, 1037, 1038, 1041, 1042, 1046, 1047, 1048, 1056, 1060, 1061,
                           1062, 1064, 1067, 1068, 1072, 1073, 1080, 1085, 1090, 1091, 1100, 1109, 1110, 1116, 1118,
                           1124, 1125, 1126, 1128, 1130, 1134, 1135, 1137, 1150, 1152, 1157, 1159, 1160, 1164, 1165,
                           1172, 1173, 1174, 1176, 1177, 1180, 1186, 1187, 1197, 1198, 1208, 1210, 1211, 1218, 1221,
                           1224, 1225, 1238, 1242, 1246, 1247, 1252, 1254, 1255, 1258, 1263, 1264, 1270, 1272, 1273,
                           1280, 1281, 1286, 1287, 1296, 1297, 1299, 1300, 1302, 1304, 1305, 1314, 1316, 1317, 1321,
                           1322, 1324, 1327, 1332, 1333, 1340, 1341, 1349, 1350, 1352, 1361, 1364, 1370, 1377, 1386,
                           1387, 1391, 1395, 1396, 1400, 1404, 1405, 1406, 1409, 1412, 1428, 1429, 1433, 1434, 1437,
                           1438, 1441, 1442, 1446, 1447, 1455, 1456, 1457, 1458, 1464, 1465, 1466, 1471, 1472, 1473,
                           1474, 1480, 1481, 1493, 1496, 1497, 1509, 1510, 1516, 1519, 1521, 1529, 1530, 1541, 1542,
                           1547, 1550, 1551, 1554, 1555, 1558, 1559, 1567, 1568, 1588, 1590, 1591, 1596, 1597, 1604,
                           1611, 1614, 1615, 1621, 1626, 1627, 1630, 1631, 1636, 1648, 1665, 1670, 1671, 1672, 1677,
                           1678, 1685, 1692, 1695, 1696, 1698, 1699, 1706, 1707, 1708, 1710, 1711, 1713, 1714, 1718,
                           1721, 1722, 1725, 1732, 1738, 1740, 1741, 1749, 1750, 1751, 1754, 1765, 1768, 1769, 1770,
                           1771, 1774, 1779, 1780, 1785, 1792, 1798, 1799, 1800, 1803, 1805, 1806, 1808, 1811, 1813,
                           1815, 1816, 1817, 1821, 1841, 1842, 1849, 1851, 1852, 1857, 1858, 1866, 1870, 1872, 1879,
                           1887, 1890, 1896, 1899, 1905, 1908, 1909, 1915, 1928, 1936, 1937, 1938, 1940, 1941, 1954,
                           1958, 1961, 1972, 1973, 1979, 1980, 1982, 1994, 1997, 2003, 2004, 2005, 2008, 2009, 2016,
                           2017, 2019, 2024, 2026, 2028, 2030, 2031, 2039, 2040, 2051, 2053, 2057, 2062, 2063, 2081,
                           2082, 2083, 2094, 2109, 2110, 2111, 2115, 2128, 2130, 2144, 2148, 2149, 2153, 2162, 2163,
                           2176, 2181, 2182, 2183, 2189, 2201, 2207, 2219, 2252, 2253, 2259, 2266, 2277, 2289, 2291,
                           2297, 2301, 2302, 2307, 2312, 2314, 2315, 2320, 2325, 2337, 2346, 2347, 2349, 2364, 2369,
                           2370, 2371, 2373]
            load_list = [185, 180, 184, 45, 18, 183, 1712, 2221, 681, 17, 1904, 2336, 131, 1504, 1016, 1175, 1947, 467,
                         67, 1505, 1059, 1779, 1565, 16, 790, 501, 1490, 277, 664, 892, 2383, 2372, 330, 331, 299, 1107,
                         485, 1706, 328, 329, 493, 2096, 626, 1600, 502, 912, 2373, 1060, 2087, 462, 1708, 1020, 804,
                         494, 1106, 754, 63, 603, 515, 483, 491, 125, 64, 615, 911, 2339, 1587, 366, 425, 105, 235, 104,
                         365, 234, 186, 139, 132, 2368, 514, 311, 820, 914, 1244, 508, 1249, 1976, 482, 1234, 878, 665,
                         281, 192, 455, 468, 834, 1027, 1029, 2159, 2328, 1329, 1974, 286, 1324, 140, 1707, 1932, 1250,
                         2012, 2027, 457, 1039, 904, 1508, 1543, 1918, 755, 250, 456, 463, 505, 507, 604, 795, 929,
                         2312, 705, 699, 1572, 1768, 1097, 111, 1995, 504, 1190, 2006, 919, 623, 2203, 29, 30, 556, 670,
                         1549, 1745, 1815, 630, 651, 127, 274, 1749, 1009, 126, 1276, 1876, 678, 679, 376, 2141, 2323,
                         278, 279, 379, 2011, 2326, 2197, 2267, 226, 478, 497, 498, 1759, 2018, 1966, 787, 907, 1363,
                         1739, 1873, 1986, 2099, 684, 1030, 43, 44, 712, 2194, 2256, 2300, 2306, 1051, 1203, 2303, 2343,
                         395, 465, 1195, 2363, 1291, 275, 1795, 2043, 1435, 1546, 1912, 2095, 57, 2126, 2191, 2264,
                         2272, 2338, 2360, 1875, 1970, 703, 383, 475, 489, 901, 1260, 420, 1622, 948, 525, 1871, 891,
                         1211, 58, 1489, 1981, 2131, 2310, 2317, 2353, 2376, 385, 545, 578, 628, 709, 750, 1512, 1573,
                         964, 1701, 1977, 2015, 861, 2047, 1845, 499, 251, 252, 300, 306, 454, 461, 464, 657, 1613,
                         1726, 289, 295, 796, 1653, 1698, 536, 31, 1416, 2275, 2299, 2331, 1326, 1686, 259, 416, 413,
                         1965, 648, 908, 1476, 1699, 1933, 1788, 1340, 1380, 1999, 349, 434, 524, 1737, 713, 720, 1356,
                         471, 407, 1658, 1266, 809, 2118, 2119, 2192, 1444, 224, 254, 1927, 2008, 547, 719, 730, 1467,
                         1640, 2051, 350, 2354, 1769, 2237, 2263, 1724, 1921, 1620, 1807, 729, 1142, 808, 838, 1193,
                         2356, 2167, 2168, 1710, 955, 1229, 1482, 2308, 411, 481, 748, 849, 1024, 1202, 1617, 1674,
                         2001, 2010, 223, 2361, 1730, 1015, 1469, 2171, 2352, 585, 945, 1719, 2104, 202, 307, 346, 423,
                         490, 503, 1232, 1688, 1717, 2033, 835, 865, 2347, 103, 619, 718, 351, 427, 1664, 1215, 2160,
                         2218, 2247, 2269, 2098, 543, 952, 1014, 1290, 1358, 1367, 304, 337, 388, 428, 1538, 345, 641,
                         988, 1187, 1366, 296, 639, 1066, 1461, 1847, 1935, 858, 1058, 1240, 2205, 2345, 2057, 860,
                         2232, 1709, 1989, 290, 292, 506, 225, 1894, 647, 649, 1278, 1304, 1349, 2179, 1758, 1862, 1889,
                         283, 557, 667, 1146, 1536, 2208, 2217, 2234, 2260, 2298, 1941, 2032, 2048, 632, 1357, 1992,
                         2085, 291, 334, 371, 426, 1330, 1386, 522, 2028, 1198, 1355, 1381, 1408, 1415, 1537, 2293, 441,
                         1140, 1488, 1863, 683, 959, 1820, 1971, 2055, 2100, 2147, 2211, 509, 538, 1220, 1368, 2236,
                         1696, 342, 511, 2180, 1924, 316, 758, 760, 1192, 444, 814, 815, 1472, 1481, 1517, 83, 553, 708,
                         1277, 1552, 2241, 2271, 1683, 1895, 1544, 2313, 84, 440, 1262, 1325, 1387, 1679, 2058, 762,
                         1171, 2213, 2250, 1901, 895, 1141, 1308, 1598, 1550, 2185, 2342, 549, 583, 1426, 1672, 1691,
                         1735, 1761, 1796, 2175, 2224, 890, 1289, 193, 239, 269, 294, 479, 737, 2143, 210, 1819, 1898,
                         653, 2135, 2146, 2162, 2220, 446, 1682, 253, 268, 387, 1753, 1496, 1518, 1525, 2124, 2138, 419,
                         445, 1946, 2050, 2053, 846, 1011, 1217, 1478, 1594, 352, 1733, 590, 1183, 1201, 1263, 370,
                         1720, 1744, 1854, 1930, 776, 778, 1364, 2140, 2245, 1861, 2038, 2040, 714, 1348, 1574, 775,
                         782, 1929, 1988, 2091, 2114, 2287, 276, 384, 421, 422, 484, 845, 851, 1333, 1693, 2132, 2229,
                         2233, 2238, 2246, 237, 1874, 1923, 2207, 1867, 1104, 1122, 1205, 1210, 418, 443, 561, 562, 593,
                         627, 724, 753, 1105, 1418, 325, 1657, 1843, 1928, 1993, 739, 2116, 1915, 1940, 999, 1282, 2248,
                         1770, 1805, 2002, 65, 805, 963, 1179, 1206, 1251, 1346, 1462, 1507, 1585, 591, 1527, 1579,
                         2273, 344, 771, 862, 1269, 1389, 1452, 1506, 1605, 1778, 1913, 2214, 2315, 282, 288, 813, 1293,
                         1556, 1888, 526, 537, 612, 613, 1223, 2161, 2206, 2240, 2283, 2371, 2379, 2052, 273, 886, 1312,
                         1450, 1477, 1528, 1578, 1596, 1882, 1883, 2021, 372, 487, 552, 2278, 386, 566, 658, 1685, 1689,
                         1743, 1879, 1975, 2106, 2107, 2110, 424, 588, 769, 850, 1145, 1160, 2226, 1996, 2046, 982,
                         1138, 2348, 2359, 1751, 198, 429, 1750, 572, 947, 983, 1077, 1089, 1399, 1487, 10, 218, 264,
                         265, 287, 401, 496, 533, 563, 635, 722, 763, 1004, 1534, 1609, 1837, 2044, 245, 702, 740, 1673,
                         1727, 1767, 1830, 1905, 1957, 2088, 2295, 2344, 214, 367, 390, 404, 41, 42, 688, 689, 1150,
                         1360, 2223, 2239, 2251, 2279, 2329, 2350, 1828, 957, 1419, 1628, 2022, 2093, 756, 831, 1404,
                         1475, 1483, 1584, 2307, 1844, 394, 584, 2139, 2034, 2054, 2156, 2288, 2304, 1866, 581, 704,
                         738, 910, 2117, 2244, 2249, 2370, 1687, 228, 392, 542, 686, 1433, 1533, 1667, 520, 631, 900,
                         1147, 1519, 2209, 1910, 1994, 206, 240, 247, 324, 340, 369, 389, 486, 495, 792, 877, 894, 1169,
                         203, 87, 830, 1037, 1079, 1132, 1177, 1204, 1286, 1473, 1593, 229, 341, 560, 600, 633, 642,
                         650, 700, 706, 707, 741, 847, 852, 1136, 1434, 1453, 1619, 1731, 1741, 1951, 1979, 2137, 2230,
                         2235, 2255, 2375, 559, 629, 889, 1170, 1700, 1939, 1952, 2039, 460, 694, 1258, 1345, 1417,
                         1575, 1967, 260, 2121, 2210, 1818, 1643, 1960, 1102, 1133, 1320, 2120, 2142, 2172, 2200, 1897,
                         1973, 625, 685, 785, 873, 1184, 267, 381, 1616, 1675, 913, 1247, 1372, 1385, 1388, 1411, 1514,
                         1787, 674, 766, 968, 1075, 1342, 1542, 212, 241, 255, 353, 368, 437, 480, 492, 1859, 962, 1678,
                         85, 86, 93, 1033, 1087, 1176, 1191, 1567, 2127, 2176, 2228, 2259, 2346, 238, 323, 551, 589,
                         673, 735, 884, 906, 979, 1128, 1241, 1637, 1723, 1725, 1757, 1773, 1784, 1810, 1869, 1916,
                         2000, 2026, 2056, 643, 1155, 1332, 2125, 1611, 189, 571, 620, 905, 954, 1080, 1403, 2193, 1868,
                         1925, 2094, 841, 902, 1110, 1375, 1590, 2374, 378, 1662, 1697, 671, 677, 1053, 2316, 315, 333,
                         410, 1635, 1794, 1804, 1945, 2115, 209, 1630, 1772, 1832, 1855, 1969, 2108, 690, 772, 917,
                         1010, 1390, 1513, 272, 399, 1742, 2013, 2086, 1163, 1267, 1547, 249, 377, 398, 400, 451, 453,
                         476, 477, 1684, 1824, 1864, 816, 1012, 1185, 396, 406, 1983, 2097, 580, 867, 1038, 1295, 1309,
                         2122, 2129, 2262, 2266, 2320, 2321, 2322, 2355, 1893, 1294, 1391, 216, 408, 124, 575, 594, 605,
                         618, 660, 839, 859, 1103, 1497, 1625, 1716, 1785, 1793, 1834, 1886, 2004, 2177, 2351, 211, 393,
                         97, 652, 794, 872, 965, 1540, 1541, 1571, 1582, 2225, 2265, 1728, 1856, 2041, 973, 1516, 1603,
                         1606, 1954, 1998, 297, 875, 1233, 2144, 2311, 2324, 1602, 1799, 2045, 586, 783, 1771, 266, 534,
                         837, 1301, 1336, 2123, 2309, 2349, 1607, 1690, 1746, 1782, 1884, 1985, 570, 624, 1510, 2190,
                         195, 285, 347, 382, 2036, 853, 930, 943, 1061, 1149, 1214, 1393, 1410, 1429, 1479, 1493, 1860,
                         1900, 1953, 610, 693, 993, 1182, 1495, 2152, 2173, 2199, 2212, 2253, 2294, 2334, 231, 232, 261,
                         528, 1850, 1852, 883, 896, 1168, 1576, 532, 868, 1032, 1036, 1297, 1660, 1964, 2082, 314, 548,
                         601, 636, 654, 666, 746, 887, 998, 1082, 1283, 1328, 1379, 1509, 1580, 1641, 1652, 1694, 1817,
                         1829, 1931, 1936, 2003, 2007, 2035, 2103, 2222, 188, 230, 380, 412, 469, 1054, 1612, 1756, 305,
                         521, 544, 768, 1091, 1186, 1296, 2195, 1734, 1849, 1959, 293, 512, 1117, 1242, 1254, 1284,
                         1322, 1633, 1833, 207, 1526, 1702, 1926, 2042, 616, 731, 1623, 1627, 1826, 1841, 187, 257, 313,
                         317, 320, 409, 458, 459, 466, 621, 637, 773, 798, 842, 1090, 1094, 1310, 2285, 2286, 1729,
                         1781, 298, 743, 899, 1056, 1492, 1515, 2270, 196, 197, 205, 215, 358, 1666, 95, 723, 759, 980,
                         994, 1235, 1236, 1338, 1663, 2049, 540, 582, 698, 1530, 1614, 640, 696, 721, 870, 1034, 1088,
                         1126, 1224, 1287, 1447, 1474, 326, 745, 1074, 1245, 1529, 1738, 1765, 1801, 1839, 1937, 222,
                         430, 529, 725, 1055, 1143, 1313, 1441, 2145, 2174, 2292, 2335, 2337, 2364, 1943, 764, 866,
                         1347, 1655, 1661, 1754, 303, 1398, 1458, 1634, 1703, 301, 431, 438, 1099, 1118, 1181, 1990,
                         2037, 190, 191, 302, 318, 363, 752, 2178, 1963, 558, 577, 669, 692, 715, 1216, 1597, 2198,
                         2215, 2216, 2219, 2274, 2290, 2301, 1626, 1711, 1764, 415, 918, 1125, 1566, 1776, 1962, 596,
                         1668, 1714, 1917, 810, 828, 976, 1067, 1113, 1116, 1374, 2318, 201, 227, 256, 510, 527, 1806,
                         1997, 1002, 1035, 1124, 1446, 1471, 1551, 123, 567, 602, 611, 747, 761, 770, 780, 802, 1154,
                         1457, 1604, 1624, 1638, 1718, 1763, 1789, 1798, 1803, 1821, 1836, 1938, 1949, 2101, 2102, 2128,
                         2289, 405, 1438, 1485, 1588, 1792, 1800, 1892, 2105, 263, 1172, 1174, 2136, 2333, 1816, 1870,
                         1934, 391, 433, 609, 995, 1255, 1402, 1420, 1421, 1424, 1430, 1436, 308, 414, 500, 523, 530,
                         1083, 1084, 1148, 1173, 1228, 1351, 2155, 2341, 765, 2130, 2150, 2196, 2242, 2282, 2296, 2297,
                         1950, 2029, 442, 882, 1144, 1968, 711, 2332, 448, 925, 1072, 1197, 1659, 788, 803, 843, 1316,
                         1553, 1639, 597, 598, 749, 1005, 2148, 550, 638, 646, 655, 736, 774, 857, 920, 1078, 1285,
                         1337, 1671, 1755, 1760, 1808, 1809, 1831, 1853, 1857, 656, 697, 1955, 2083, 402, 1369, 397,
                         1858, 607, 732, 781, 942, 1026, 1073, 1137, 1268, 1270, 1406, 2358, 221, 258, 327, 335, 403,
                         447, 452, 473, 474, 531, 832, 1130, 2254, 2277, 339, 1752, 2184, 1610, 1680, 1721, 2030, 554,
                         555, 592, 784, 818, 823, 1428, 922, 1280, 1409, 1442, 1480, 1599, 270, 271, 1827, 599, 871,
                         359, 360, 472, 1677, 1715, 961, 1535, 2149, 2183, 2252, 2305, 2319, 1642, 1704, 1791, 595, 811,
                         949, 1000, 1064, 1194, 1218, 1273, 1317, 1445, 1454, 1501, 1545, 432, 541, 573, 579, 728, 958,
                         996, 997, 1028, 1272, 1359, 1405, 1568, 1651, 1654, 1676, 1766, 1911, 2016, 2020, 824, 992,
                         1046, 1500, 1942, 2024, 742, 975, 1354, 1554, 1629, 1656, 1908, 248, 1134, 1302, 1311, 1352,
                         2231, 2284, 2382, 1891, 356, 701, 1314, 2202, 1825, 1842, 1848, 1909, 1961, 668, 676, 978,
                         1100, 1238, 2291, 417, 439, 1991, 767, 219, 220, 284, 338, 1644, 1705, 1292, 2268, 716, 717,
                         1207, 1109, 1246, 1339, 1361, 1422, 1451, 1486, 1586, 373, 574, 608, 659, 672, 710, 1327, 1427,
                         1615, 2023, 1595, 2281, 1722, 348, 354, 357, 488, 675, 1022, 2182, 2189, 2369, 2084, 217, 970,
                         1045, 1555, 2243, 233, 1165, 1303, 1331, 1437, 1464, 1978, 1608, 2005, 661, 691, 695, 757, 744,
                         779, 1221, 1377, 1414, 2201, 199, 1692, 827, 935, 939, 1076, 1156, 1237, 1425, 1259, 242, 1786,
                         897, 1041, 1042, 1071, 1086, 1139, 1463, 622, 680, 687, 733, 1645, 200, 236, 244, 343, 535,
                         109, 110, 909, 960, 1068, 2151, 2302, 606, 2154, 319, 888, 793, 951, 1001, 435, 1838, 1890,
                         1984, 436, 1395, 2327, 1646, 1813, 944, 950, 1557, 2330, 1373, 1521, 1558, 1559, 1669, 262,
                         974, 2276, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 19, 20, 21, 22, 23, 24, 25, 26, 27,
                         28, 32, 33, 34, 35, 36, 37, 38, 39, 40, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 59, 60, 61,
                         62, 66, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 88, 89, 90, 91, 92, 94, 96,
                         98, 99, 100, 101, 102, 106, 107, 108, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122,
                         128, 129, 130, 133, 134, 135, 136, 137, 138, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150,
                         151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169,
                         170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 181, 182, 194, 204, 243, 280, 309, 310, 312,
                         321, 322, 332, 336, 355, 361, 362, 374, 375, 449, 450, 470, 513, 516, 517, 518, 519, 539, 546,
                         564, 565, 568, 569, 576, 587, 614, 617, 634, 644, 645, 662, 663, 682, 726, 727, 734, 751, 777,
                         786, 789, 791, 797, 799, 800, 801, 806, 807, 812, 817, 819, 821, 822, 825, 826, 829, 833, 836,
                         840, 844, 848, 854, 855, 856, 863, 864, 869, 874, 876, 879, 880, 881, 885, 893, 898, 903, 915,
                         916, 921, 923, 924, 926, 927, 928, 931, 932, 933, 934, 936, 937, 938, 940, 941, 946, 953, 956,
                         966, 967, 969, 971, 972, 977, 981, 984, 985, 986, 987, 989, 990, 991, 1003, 1006, 1007, 1008,
                         1013, 1017, 1018, 1019, 1021, 1023, 1025, 1031, 1040, 1043, 1044, 1047, 1048, 1049, 1050, 1052,
                         1057, 1062, 1063, 1065, 1069, 1070, 1081, 1085, 1092, 1093, 1095, 1096, 1098, 1101, 1108, 1111,
                         1112, 1114, 1115, 1119, 1120, 1121, 1123, 1127, 1129, 1131, 1135, 1151, 1152, 1153, 1157, 1158,
                         1159, 1161, 1162, 1164, 1166, 1167, 1178, 1180, 1188, 1189, 1196, 1199, 1200, 1208, 1209, 1212,
                         1213, 1219, 1222, 1225, 1226, 1227, 1230, 1231, 1239, 1243, 1248, 1252, 1253, 1256, 1257, 1261,
                         1264, 1265, 1271, 1274, 1275, 1279, 1281, 1288, 1298, 1299, 1300, 1305, 1306, 1307, 1315, 1318,
                         1319, 1321, 1323, 1334, 1335, 1341, 1343, 1344, 1350, 1353, 1362, 1365, 1370, 1371, 1376, 1378,
                         1382, 1383, 1384, 1392, 1394, 1396, 1397, 1400, 1401, 1407, 1412, 1413, 1423, 1431, 1432, 1439,
                         1440, 1443, 1448, 1449, 1455, 1456, 1459, 1460, 1465, 1466, 1468, 1470, 1484, 1491, 1494, 1498,
                         1499, 1502, 1503, 1511, 1520, 1522, 1523, 1524, 1531, 1532, 1539, 1548, 1560, 1561, 1562, 1563,
                         1564, 1569, 1570, 1577, 1581, 1583, 1589, 1591, 1592, 1601, 1618, 1621, 1631, 1632, 1636, 1647,
                         1648, 1649, 1650, 1665, 1670, 1681, 1695, 1713, 1732, 1736, 1740, 1747, 1748, 1762, 1774, 1775,
                         1777, 1780, 1783, 1790, 1797, 1802, 1811, 1812, 1814, 1822, 1823, 1835, 1840, 1846, 1851, 1865,
                         1872, 1877, 1878, 1880, 1881, 1885, 1887, 1896, 1899, 1902, 1903, 1906, 1907, 1914, 1919, 1920,
                         1922, 1944, 1948, 1956, 1958, 1972, 1980, 1982, 1987, 2009, 2014, 2017, 2019, 2025, 2031, 2059,
                         2060, 2061, 2062, 2063, 2064, 2065, 2066, 2067, 2068, 2069, 2070, 2071, 2072, 2073, 2074, 2075,
                         2076, 2077, 2078, 2079, 2080, 2081, 2089, 2090, 2092, 2109, 2111, 2112, 2113, 2133, 2134, 2153,
                         2157, 2158, 2163, 2165, 2166, 2169, 2170, 2181, 2186, 2187, 2188, 2204, 2227, 2257, 2258, 2261,
                         2280, 2314, 2325, 2340, 2357, 2362, 2365, 2366, 2367, 2377, 2378, 2380, 2381, 2164, 213, 364,
                         208, 246]

        degree_list = degree_list[0:int(var * len(degree_list))]
        load_list = load_list[0:int(var * len(load_list))]

        # print(degree_list)
        # print(load_list)

        init_attack_list = list(set(degree_list + load_list))
        # print(len(init_attack_list))

        init_population_list = []

        init_f1 = []
        init_f2 = []
        for i in range(self.population_list_num):
            attack_list = random.sample(init_attack_list, self.attack_num)
            single_popu_list = individual(0, 0, [], 0, 0, 0, attack_list)
            init_population_list.append(copy.deepcopy(single_popu_list))

            # 计算rp和sn
            a1, a2, a3, a4, a5 = self.attack_with_cal(init_population_list[i].attack_list)
            self.f1 = a2
            self.f2 = a4
            init_f1.append(a2)
            init_f2.append(a4)

        self.fast_non_dominated_sort(init_population_list)

        pc = 0.5
        pm = 0.8
        return init_population_list, pc, pm, init_attack_list, init_f1, init_f2

    def dominate(self, p1, p2):
        if p1.f1 <= p2.f1 and p1.f2 <= p2.f2:
            return True
        return False

    def fast_non_dominated_sort(self, population_list):
        F = []
        F1 = []
        for p in population_list:
            p.dominate_list = []
            p.be_dominated = 0
            for q in population_list:
                if self.dominate(p, q):
                    p.dominate_list.append(q)
                elif self.dominate(q, p):
                    p.be_dominated += 1
                else:
                    pass

            # print(p.f1,p.dominate_list,p.be_dominated)

            if p.be_dominated == 0:
                p.rank = 1
                F1.append(p)
        F.append(F1)

        i = 0
        while len(F[i]) > 0:
            Q = []
            for p in F[i]:
                # print(p.dominate_list)
                for q in p.dominate_list:
                    q.be_dominated -= 1
                    if q.be_dominated == 0:
                        q.rank = i + 2
                        Q.append(q)
            F.append(Q)
            i += 1
        return F

    def sort_by_object(self, partial_list, m):
        # 根据f1排序
        if m == 1:
            partial_list.sort(key=lambda x: x.f1)
        # 根据f2排序
        else:
            partial_list.sort(key=lambda x: x.f2)

        return partial_list

    def crowding_distance_sort(self, partial_list):
        if len(partial_list) == 1:
            return partial_list

        l = len(partial_list)
        for i in range(l):
            partial_list[i].crowding_distance = 0
        for i in range(2):
            partial_list = self.sort_by_object(partial_list, i + 1)

            partial_list[0].crowding_distance = 10000
            partial_list[-1].crowding_distance = 10000
            # f1
            if i == 0:
                fmax = partial_list[-1].f1
                fmin = partial_list[0].f1
                for j in range(1, l - 1):
                    if fmax == fmin:
                        continue
                    temp = (partial_list[j + 1].f1 - partial_list[j - 1].f1) / (fmax - fmin)
                    partial_list[j].crowding_distance += temp
            # f2
            else:
                fmax = partial_list[-1].f2
                fmin = partial_list[0].f2
                for j in range(1, l - 1):
                    if fmax == fmin:
                        continue
                    temp = (partial_list[j + 1].f2 - partial_list[j - 1].f2) / (fmax - fmin)
                    partial_list[j].crowding_distance += temp

        partial_list.sort(key=lambda x: x.crowding_distance, reverse=True)
        return partial_list

    def crossover_operation(self, population_list, pc, init_attack_list):
        # print(len(population_list))
        parent_child_list = copy.deepcopy(population_list)
        # 生成一个0-19，大小为20的序列
        list = np.arange(len(population_list)).tolist()

        tag_list = []
        for i in range(len(init_attack_list)):
            tag_list.append(init_attack_list[i])
        # print('hey:',tag_list)
        # print(list)
        # print(int(len(population_list)/2))
        for i in range(int(len(population_list) / 2)):
            a, b = random.sample(list, 2)
            # 删除已选择的两个个体
            list.remove(a)
            list.remove(b)
            # print(list)
            child_a = copy.deepcopy(population_list[a])
            child_b = copy.deepcopy(population_list[b])
            attack_list_a, attack_list_b, flag = self.crossover(copy.deepcopy(child_a.attack_list),
                                                                copy.deepcopy(child_b.attack_list), pc,
                                                                init_attack_list)
            # print(child_a,child_b)

            # 重组之后attack_list没有变化,则随机从外面选一个
            if set(attack_list_a) == set(child_a.attack_list) and np.random.uniform(0, 1) > 0.5 and flag:
                tag = copy.deepcopy(tag_list)
                for i in range(len(attack_list_a)):
                    if attack_list_a[i] in tag:
                        tag.remove(attack_list_a[i])
                remove_node = random.sample(attack_list_a, 2)
                attack_list_a.remove(remove_node[0])
                attack_list_a.remove(remove_node[1])

                add_node = random.sample(tag, 2)
                attack_list_a.append(add_node[0])
                attack_list_a.append(add_node[1])

            if set(attack_list_b) == set(child_b.attack_list) and np.random.uniform(0, 1) > 0.5 and flag:
                tag = copy.deepcopy(tag_list)
                for i in range(len(attack_list_b)):
                    if attack_list_b[i] in tag:
                        tag.remove(attack_list_b[i])
                remove_node = random.sample(attack_list_b, 2)
                attack_list_b.remove(remove_node[0])
                attack_list_b.remove(remove_node[1])

                add_node = random.sample(tag, 2)
                attack_list_b.append(add_node[0])
                attack_list_b.append(add_node[1])

            child_a.attack_list = attack_list_a
            child_b.attack_list = attack_list_b

            parent_child_list.append(copy.deepcopy(child_a))
            parent_child_list.append(copy.deepcopy(child_b))
        # print(parent_child_list)
        # print(parent_child_list)
        # print(len(parent_child_list))
        return parent_child_list

    def crossover(self, population_list_a, population_list_b, pc, init_attack_list):
        # 随机将每个个体的交换两个

        length = len(population_list_a)

        child_a = population_list_a
        child_b = population_list_b
        # print(0,len(child_a),len(child_b))

        # print('pa',population_list_a)
        # print('pb',population_list_b)
        # print('before')
        # print(child_a)
        # print(child_b)
        tag = False

        if np.random.uniform(0, 1) > pc:
            # 满足基因重组条件
            # 随机挑选两个点交换
            tag = True
            cross_list_a = random.sample(population_list_a, self.crossover_num)
            cross_list_b = random.sample(population_list_b, self.crossover_num)

            i = 0
            while i < len(population_list_a):
                if population_list_a[i] in cross_list_b:
                    population_list_a.remove(population_list_a[i])
                else:
                    i += 1
            # print(1,len(child_a),len(child_b))

            for i in range(len(cross_list_b)):
                # 原有的去除
                if cross_list_a[i] in population_list_a:
                    population_list_a.remove(cross_list_a[i])
                # 新增重组的
                if cross_list_b[i] not in population_list_a:
                    population_list_a.append(cross_list_b[i])

            # print(2,len(child_a),len(child_b))

            if (len(population_list_a) < length):
                need = length - len(population_list_a)
                # 构建候选list
                under_list = []
                for i in range(len(init_attack_list)):
                    if init_attack_list[i] not in population_list_a:
                        under_list.append(init_attack_list[i])
                select_list = random.sample(under_list, need)

                for i in range(need):
                    population_list_a.append(select_list[i])

            child_a = population_list_a
            # print(3,len(child_a),len(child_b))

            i = 0
            while i < len(population_list_b):
                if population_list_b[i] in cross_list_a:
                    population_list_b.remove(population_list_b[i])
                else:
                    i += 1

            for i in range(len(cross_list_a)):
                if cross_list_b[i] in population_list_b:
                    population_list_b.remove(cross_list_b[i])
                if cross_list_a[i] not in population_list_b:
                    population_list_b.append(cross_list_a[i])

            if (len(population_list_b) < length):
                need = length - len(population_list_b)
                # 构建候选list
                under_list = []
                for i in range(len(init_attack_list)):
                    if init_attack_list[i] not in population_list_b:
                        under_list.append(init_attack_list[i])
                select_list = random.sample(under_list, need)
                for i in range(need):
                    population_list_b.append(select_list[i])

            child_b = population_list_b


        return child_a, child_b, tag

    def mutation(self, population_list, pm, init_attack_list):
        for i in range(len(population_list)):
            # 达到变异条件
            if i < len(population_list) / 2:
                continue
            if np.random.uniform(0, 1) > pm:
                # 构建候选点
                under_list = []
                for k in range(len(init_attack_list)):
                    if init_attack_list[k] not in population_list[i].attack_list:
                        under_list.append(init_attack_list[k])
                delete_node_id = random.sample(population_list[i].attack_list, 1)
                # print(delete_node_id)
                # print(population_list[i])
                population_list[i].attack_list.remove(delete_node_id[0])
                add_node_id = random.sample(under_list, 1)
                population_list[i].attack_list.append(add_node_id[0])
        return population_list

    def cal_function(self, population_list):
        ab_array = np.zeros((len(population_list), 4))
        # print(ab_array)
        for i in range(len(population_list)):
            a1, a2, a3, a4, a5 = self.attack_with_cal(population_list[i].attack_list)
            # 重新计算目标函数值
            population_list[i].f1 = a2
            population_list[i].f2 = a4
            ab_array[i, 0] = a1
            ab_array[i, 1] = a2
            ab_array[i, 2] = a3
            ab_array[i, 3] = a4
        # print(a5)

        return population_list, ab_array

    def cal_matrix(self, g):
        matrix = np.zeros((self.size, self.size), dtype=int)

        for item in g.branch:
            i = int(item[0]) - 1
            j = int(item[1]) - 1
            matrix[i, j] = matrix[j, i] = 1

        return matrix

    def cal_n_c(self, matrix1):

        eig_list, eig_vec = np.linalg.eig(matrix1)
        eig_list = eig_list.astype(np.float64)

        temp_sum = 0
        for i in range(len(eig_list)):
            temp_sum += np.exp(eig_list[i])

        natural_connectivity = np.log(temp_sum / len(matrix1))
        return natural_connectivity

    def attack_with_cal(self, attack_list):
        if self.size == 118:
            G = case118()
        elif self.size == 300:
            G = case300()
        elif self.size == 500:
            G = case500()
        elif self.size == 2383:
            G = case2383()


        g = Power_Graph()
        new_case = g.case_preprocess(G)
        g.init_by_case(G)
        g.set_ramp_rate(0.3)

        matrix1 = self.cal_matrix(g)
        natural_connectivity_format = self.cal_n_c(matrix1)

        # print(g.edge_list)

        for k in attack_list:
            # print(k)
            g.delete_bus(k)

        cf = Power_Failure(g)
        cf.failure_process()

        matrix2 = self.cal_matrix(g)
        natural_connectivity_last = self.cal_n_c(matrix2)

        ini_g = Power_Graph()
        ini_g.init_by_case(G)

        gr = Attack(cf.steady_list, ini_g, cf.isolate_list)

        # 画图
        # g.draw_graph_list(gr.steady_list)

        residual_node = 0
        max_subgraph_node = 0
        for sub_graph in gr.steady_list:
            if max_subgraph_node < len(sub_graph.bus_id):
                max_subgraph_node = len(sub_graph.bus_id)
            residual_node += len(sub_graph.bus_id)

        rn_decrease_per = residual_node / self.size
        max_subgraph_node_decrease_per = max_subgraph_node / self.size

        nc_decrease_per = (natural_connectivity_format - natural_connectivity_last) / natural_connectivity_format
        rp_decrease_per = gr.cal_residual_power()
        return nc_decrease_per, rp_decrease_per, rn_decrease_per, max_subgraph_node_decrease_per, g.degree

    def find_the_best(self, population_list, F):
        return F[0]

    def discard_same(self, population_list, init_attack_list):
        attack_lists = []
        for i in range(len(population_list)):
            attack_list = population_list[i].attack_list
            attack_lists.append(sorted(attack_list))

        length1 = len(population_list)

        # print('before:',len(attack_lists))
        # print('-----')
        # print(attack_lists)

        attack_lists = list(set(tuple(t) for t in attack_lists))
        attack_lists = [list(v) for v in attack_lists]

        # print('final:',len(attack_lists))
        # print('-----')
        # print(attack_lists)

        # 设置候选节点集

        while len(attack_lists) < length1:
            attack_list = random.sample(init_attack_list, self.attack_num)
            attack_lists.append(attack_list)

        # print(attack_lists)
        # print(len(attack_lists))

        for i in range(len(population_list)):
            population_list[i].attack_list = copy.deepcopy(attack_lists[i])
        # print(population_list[i].attack_list)

        return population_list

    def main(self, t, var):
        population_list, pc, pm, init_attack_list, init_f1, init_f2 = self.begin4(var)

        # 循环迭代500次
        flag = True
        iter = 0
        after_F = []
        k = 0
        while flag:
            print('\nt,iter,k：', t, iter, k)

            before_F = copy.deepcopy(after_F)
            population_list = self.crossover_operation(population_list, pc, init_attack_list)

            # 执行变异操作
            # list包含parent和child
            population_list = self.mutation(population_list, pm, init_attack_list)

            population_list = self.discard_same(population_list, init_attack_list)

            # 此时的population_list是已经经过变异操作的个体种群
            # 计算目标函数值
            population_list, ab_array = self.cal_function(population_list)

            F = self.fast_non_dominated_sort(population_list)
            # print(F)
            i = 0
            f1_list = []
            f2_list = []
            while len(F[i]) > 0:
                for j in range(len(F[i])):
                    f1_list.append(F[i][j].f1)
                    f2_list.append(F[i][j].f2)
                i += 1


            new_population_list = []
            i = 0
            # 没有超过种群总限制时，直接将Fi加入
            while len(new_population_list) + len(F[i]) <= self.population_list_num:
                for j in range(len(F[i])):
                    new_population_list.append(F[i][j])
                i += 1
            if len(new_population_list) < self.population_list_num:
                need = self.population_list_num - len(new_population_list)
                # 直接使用i，不用+1页不用-1
                # 对fi进行拥挤距离计算
                F[i] = self.crowding_distance_sort(F[i])
                # print(F[i])
                j = 0
                while j < need:
                    new_population_list.append(F[i][j])
                    j += 1
            population_list = new_population_list
            after_F = copy.deepcopy(F[0])
            best_list = self.find_the_best(population_list, F)
            # print('best_list len:',len(best_list))

            # 判断是否收敛
            tag = self.converge(before_F, after_F)

            if tag:
                k += 1
            else:
                k = 0

            iter += 1
            # print(before_F,after_F)

            if tag and k >= 30 or iter >= 500:
                print("---")
                print("iter:", iter)
                print("---")
                # print(before_F)
                # print(after_F)
                flag = False

        # for i in range(len(best_list)):
        # 	print('here:',best_list[i].f1,best_list[i].f2)
        # print('done')
        # for i in range(len(population_list)):
        # 	print(population_list[i],cal_route_length(population_list[i],dist))
        best_list = self.find_the_best(population_list, F)

        return best_list, population_list, ab_array, iter, init_f1, init_f2

    def converge(self, before_F, after_F):
        # 数据预处理
        before_attack_list = []
        after_attack_list = []
        for i in range(len(before_F)):
            # print(type(before_F[i].attack_list))
            before_attack_list.append(sorted(before_F[i].attack_list))
        # print("111:",before_F[i].attack_list)

        for i in range(len(after_F)):
            after_attack_list.append(sorted(after_F[i].attack_list))


        before_attack_list = list(set(tuple(t) for t in before_attack_list))
        before_attack_list = [list(v) for v in before_attack_list]

        after_attack_list = list(set(tuple(t) for t in after_attack_list))
        after_attack_list = [list(v) for v in after_attack_list]


        len1 = len(before_attack_list)
        len2 = len(after_attack_list)
        if len1 != len2 or len1 == len2 == 0:
            return False

        # print(before_attack_list)
        # print(after_attack_list)

        # print(before_F[0])
        flag = True
        for f in before_attack_list:
            if f not in after_attack_list:
                flag = False
                return flag
        return flag


def calhv(best_list):
    f_list = []
    for i in range(len(best_list)):
        a = best_list[i].f1
        b = best_list[i].f2
        temp = (a, b)
        f_list.append(temp)
    # print(f_list)
    f_list = sorted(f_list)
    hv = 0
    for i in range(len(f_list) - 1):
        hv = hv + (f_list[i + 1][0] - f_list[i][0]) * f_list[i][1]
    # leftest one
    hv = hv + f_list[0][0]

    # rightest one
    hv = hv + (1 - f_list[-1][0]) * f_list[-1][1]

    hv = 1 - hv

    return hv


def doc(t, var):

    nsga = nsga2(300,10,5,500,60)

    best_list, population_list, ab_array, iter, init_f1, init_f2 = nsga.main(t, var)

    hv = calhv(best_list)
    print('hv:', hv)

    f1_list = []
    f2_list = []
    attack_lists = []
    print('--best_list---')
    print(len(best_list))
    for i in range(len(best_list)):
        print(best_list[i].attack_list)
        print(best_list[i].f1, best_list[i].f2)
        f1_list.append(best_list[i].f1)
        f2_list.append(best_list[i].f2)
        attack_lists.append(best_list[i].attack_list)
    print('-----')

    avg_rp = np.mean(f1_list)
    avg_msn = np.mean(f2_list)

    f3_list = []
    f4_list = []
    for i in range(len(population_list)):
        print(population_list[i].attack_list)
        print(population_list[i].f1, population_list[i].f2)
        if population_list[i] not in best_list:
            f3_list.append(population_list[i].f1)
            f4_list.append(population_list[i].f2)

 

    return iter, hv, len(best_list)


if __name__ == '__main__':

    iter_list = []
    hv_list = []
    cnt_list = []

    for i in range(50):
        iter, hv, cnt = doc(i, 0.35)
        iter_list.append(iter)
        hv_list.append(hv)
        cnt_list.append(cnt)


    print(iter_list)
    print(hv_list)
    print(cnt_list)
    print('average:', np.mean(iter_list), np.mean(hv_list), np.mean(cnt_list))