/*
 * GA.java
 *
 * Created on 26 de diciembre de 2003, 21:36
 */

package ATSP;
import java.lang.Thread;
import java.util.Vector;
import java.util.Iterator;
import java.util.TreeSet;
import java.util.Random;

/**
 *
 * @author  gabriel
 */
public class GA {
    
    private Vector poblacions;
    
    public static int [][] dist={{0, 1, 119, 896, 187, 367, 997, 690, 22, 613, 347, 874, 522, 122, 730, 486, 705, 823, 232, 463, 554, 589, 675, 325, 970, 1000, 407, 776, 276, 123, 331, 356, 361, 305, 798, 47, 427, 645, 439, 139, 91, 247, 650, 211, 10, 100, 838, 627, 725, 760, },
        {843, 0, 776, 137, 475, 977, 937, 718, 101, 99, 281, 609, 751, 819, 530, 97, 240, 975, 248, 226, 768, 241, 31, 584, 613, 348, 881, 475, 367, 178, 712, 641, 410, 898, 157, 250, 824, 391, 242, 101, 472, 636, 722, 87, 775, 652, 371, 867, 337, 54, },
        {885, 509, 0, 204, 989, 594, 129, 226, 597, 226, 513, 921, 201, 537, 227, 112, 82, 959, 296, 392, 802, 709, 537, 940, 943, 943, 997, 79, 642, 922, 205, 361, 551, 947, 904, 861, 400, 937, 250, 754, 586, 872, 631, 636, 752, 459, 510, 390, 542, 141, },
        {576, 111, 550, 0, 588, 504, 6, 702, 155, 20, 723, 179, 723, 770, 667, 95, 829, 598, 487, 885, 590, 239, 370, 37, 823, 898, 173, 923, 56, 261, 977, 786, 681, 46, 689, 438, 933, 116, 809, 503, 587, 603, 686, 194, 466, 341, 356, 545, 784, 52, },
        {862, 810, 223, 260, 0, 541, 197, 61, 213, 416, 462, 62, 62, 205, 203, 152, 269, 913, 160, 267, 747, 249, 174, 187, 700, 174, 114, 939, 412, 519, 905, 56, 109, 381, 369, 551, 525, 128, 987, 812, 660, 753, 149, 544, 764, 684, 396, 830, 905, 725, },
        {30, 330, 384, 115, 981, 0, 38, 483, 445, 176, 619, 570, 648, 891, 896, 446, 658, 567, 306, 646, 806, 229, 800, 893, 612, 723, 354, 771, 300, 329, 174, 279, 751, 253, 126, 262, 603, 802, 665, 861, 209, 127, 308, 131, 308, 460, 677, 290, 863, 296, },
        {292, 172, 444, 158, 295, 241, 0, 413, 301, 72, 958, 321, 694, 981, 594, 797, 145, 507, 819, 715, 672, 512, 638, 892, 645, 76, 915, 22, 879, 643, 14, 866, 975, 74, 185, 508, 466, 243, 511, 776, 767, 326, 579, 694, 496, 662, 119, 17, 829, 654, },
        {858, 129, 547, 662, 801, 123, 28, 0, 182, 269, 554, 113, 421, 293, 685, 410, 470, 850, 77, 237, 264, 552, 624, 117, 961, 45, 55, 42, 254, 722, 880, 710, 921, 110, 809, 800, 680, 618, 554, 129, 62, 887, 573, 692, 568, 604, 37, 35, 910, 963, },
        {632, 108, 211, 411, 67, 426, 763, 104, 0, 568, 208, 681, 542, 814, 248, 514, 237, 326, 922, 41, 678, 909, 392, 192, 516, 59, 422, 352, 582, 678, 327, 885, 97, 596, 378, 400, 362, 411, 124, 746, 376, 535, 167, 82, 680, 399, 679, 412, 330, 636, },
        {613, 983, 345, 360, 181, 120, 576, 870, 698, 0, 808, 312, 4, 122, 391, 158, 810, 476, 819, 873, 958, 477, 209, 857, 717, 681, 359, 3, 895, 167, 419, 337, 504, 134, 588, 198, 719, 219, 323, 151, 341, 717, 965, 181, 859, 39, 456, 191, 760, 652, },
        {135, 293, 390, 90, 780, 319, 496, 516, 1, 156, 0, 906, 11, 171, 526, 437, 335, 164, 74, 142, 968, 876, 701, 265, 409, 762, 722, 319, 356, 780, 833, 41, 512, 33, 977, 720, 782, 887, 974, 907, 116, 551, 334, 732, 400, 969, 909, 679, 255, 228, },
        {32, 168, 222, 654, 150, 48, 100, 549, 611, 260, 851, 0, 112, 766, 450, 771, 925, 386, 240, 791, 375, 850, 875, 635, 299, 317, 969, 50, 215, 426, 435, 791, 648, 93, 515, 185, 351, 582, 582, 2, 32, 411, 901, 992, 902, 188, 494, 962, 766, 620, },
        {602, 927, 494, 559, 147, 711, 418, 271, 628, 37, 219, 497, 0, 837, 892, 340, 676, 441, 63, 315, 17, 109, 781, 343, 958, 616, 985, 532, 509, 522, 608, 897, 274, 514, 819, 986, 353, 888, 932, 759, 446, 323, 981, 176, 742, 919, 883, 67, 978, 503, },
        {290, 556, 260, 716, 155, 319, 713, 471, 80, 517, 479, 105, 49, 0, 153, 88, 140, 182, 886, 645, 692, 764, 319, 950, 560, 421, 642, 141, 696, 184, 258, 698, 250, 879, 639, 9, 372, 15, 132, 992, 856, 883, 453, 188, 503, 89, 539, 916, 819, 934, },
        {126, 333, 430, 877, 598, 532, 696, 434, 597, 458, 697, 637, 52, 649, 0, 652, 290, 625, 45, 91, 638, 546, 406, 317, 324, 313, 146, 89, 181, 283, 367, 917, 501, 806, 950, 912, 802, 511, 963, 168, 144, 758, 121, 392, 584, 646, 418, 114, 879, 5, },
        {788, 989, 906, 228, 352, 131, 279, 699, 588, 386, 951, 229, 599, 621, 752, 0, 371, 740, 574, 767, 495, 848, 674, 475, 255, 662, 352, 612, 588, 858, 176, 929, 935, 467, 325, 25, 167, 593, 550, 858, 457, 557, 478, 806, 892, 776, 942, 179, 991, 428, },
        {988, 857, 866, 30, 123, 206, 86, 189, 70, 741, 186, 37, 314, 446, 163, 828, 0, 119, 63, 774, 246, 74, 383, 661, 115, 386, 163, 741, 853, 541, 458, 152, 160, 143, 227, 131, 370, 47, 918, 574, 955, 229, 416, 275, 366, 787, 176, 661, 588, 320, },
        {462, 815, 562, 699, 643, 709, 17, 458, 884, 323, 155, 286, 560, 721, 141, 907, 185, 0, 743, 528, 185, 775, 843, 898, 794, 872, 524, 433, 233, 916, 841, 888, 491, 740, 427, 410, 893, 482, 396, 42, 25, 684, 547, 917, 638, 130, 590, 904, 90, 199, },
        {506, 763, 615, 253, 65, 399, 920, 185, 968, 659, 839, 877, 828, 834, 52, 204, 145, 201, 0, 491, 416, 263, 572, 723, 623, 993, 680, 935, 228, 859, 987, 218, 602, 535, 688, 156, 228, 364, 246, 315, 935, 380, 472, 80, 449, 17, 295, 984, 914, 427, },
        {628, 675, 240, 336, 106, 244, 530, 672, 535, 582, 226, 52, 836, 487, 37, 355, 738, 547, 783, 0, 736, 572, 256, 87, 108, 251, 153, 962, 691, 836, 786, 555, 654, 678, 975, 904, 972, 904, 585, 424, 229, 871, 654, 536, 469, 749, 20, 436, 770, 949, },
        {162, 731, 90, 539, 754, 300, 267, 329, 223, 389, 928, 547, 15, 546, 637, 924, 493, 130, 208, 866, 0, 78, 357, 292, 196, 349, 729, 219, 588, 781, 556, 591, 807, 763, 316, 245, 168, 382, 514, 534, 573, 108, 381, 852, 730, 146, 883, 941, 681, 15, },
        {602, 207, 12, 270, 845, 856, 233, 262, 674, 681, 291, 431, 984, 71, 633, 211, 166, 53, 152, 895, 798, 0, 289, 620, 621, 256, 881, 764, 944, 291, 962, 850, 882, 958, 869, 74, 645, 589, 823, 450, 988, 455, 467, 800, 21, 652, 485, 818, 879, 892, },
        {478, 693, 274, 819, 991, 801, 286, 432, 276, 476, 339, 85, 815, 923, 50, 520, 478, 576, 840, 672, 914, 380, 0, 373, 972, 293, 141, 452, 285, 495, 523, 233, 123, 388, 621, 41, 101, 573, 849, 283, 226, 434, 112, 930, 773, 154, 911, 123, 718, 862, },
        {26, 530, 994, 104, 91, 779, 84, 459, 568, 823, 533, 343, 939, 246, 591, 883, 890, 227, 32, 823, 815, 32, 930, 0, 126, 386, 166, 71, 324, 907, 361, 777, 706, 764, 503, 648, 419, 322, 195, 492, 945, 508, 970, 810, 257, 659, 41, 60, 352, 882, },
        {137, 9, 192, 64, 41, 60, 380, 792, 222, 176, 52, 266, 656, 48, 612, 290, 364, 820, 199, 125, 826, 344, 652, 212, 0, 474, 511, 858, 906, 480, 438, 582, 791, 369, 259, 597, 367, 633, 243, 360, 509, 715, 818, 980, 256, 652, 118, 266, 120, 236, },
        {181, 146, 298, 50, 508, 310, 38, 387, 417, 950, 42, 94, 360, 953, 887, 799, 706, 530, 185, 422, 700, 702, 285, 835, 452, 0, 920, 386, 73, 798, 455, 530, 972, 308, 462, 186, 392, 52, 5, 549, 487, 707, 969, 943, 735, 31, 869, 141, 454, 147, },
        {570, 50, 290, 347, 683, 91, 193, 215, 374, 308, 842, 797, 191, 604, 911, 495, 31, 235, 40, 923, 788, 13, 852, 97, 742, 6, 0, 446, 183, 142, 964, 906, 112, 970, 780, 843, 676, 137, 805, 666, 625, 456, 937, 709, 719, 526, 226, 889, 297, 859, },
        {441, 669, 878, 423, 425, 62, 71, 978, 483, 288, 276, 96, 562, 304, 288, 6, 46, 587, 443, 326, 142, 561, 693, 226, 558, 124, 159, 0, 337, 896, 927, 454, 723, 119, 693, 625, 819, 871, 664, 810, 120, 105, 330, 185, 679, 906, 867, 20, 793, 218, },
        {415, 171, 605, 434, 643, 175, 354, 142, 220, 259, 746, 267, 925, 858, 510, 714, 291, 624, 938, 170, 870, 805, 285, 852, 54, 188, 56, 456, 0, 135, 218, 296, 221, 579, 777, 874, 605, 315, 604, 770, 542, 281, 405, 111, 261, 277, 650, 454, 622, 866, },
        {270, 106, 990, 29, 116, 621, 545, 177, 543, 94, 615, 273, 620, 391, 618, 611, 417, 889, 339, 13, 983, 494, 714, 536, 266, 995, 323, 853, 193, 0, 544, 221, 160, 105, 622, 415, 752, 316, 692, 636, 935, 559, 685, 341, 420, 993, 753, 693, 739, 31, },
        {110, 152, 110, 324, 324, 52, 922, 694, 114, 434, 353, 700, 120, 294, 855, 627, 402, 329, 339, 128, 285, 360, 724, 663, 665, 613, 101, 170, 579, 179, 0, 895, 126, 302, 488, 81, 311, 277, 523, 478, 68, 272, 604, 860, 973, 753, 275, 956, 489, 298, },
        {552, 211, 460, 244, 722, 564, 717, 918, 931, 791, 661, 73, 216, 866, 723, 780, 943, 779, 45, 912, 785, 567, 625, 394, 606, 834, 450, 328, 376, 419, 478, 0, 258, 32, 59, 668, 375, 909, 971, 867, 673, 507, 487, 637, 694, 367, 210, 650, 187, 697, },
        {911, 97, 39, 114, 321, 353, 234, 477, 1000, 414, 272, 194, 737, 528, 222, 493, 992, 269, 776, 542, 188, 534, 980, 649, 672, 422, 895, 461, 618, 127, 201, 778, 0, 553, 167, 959, 139, 112, 336, 206, 787, 673, 454, 7, 757, 480, 737, 987, 307, 821, },
        {346, 548, 224, 997, 978, 501, 25, 398, 837, 783, 245, 141, 462, 705, 350, 886, 756, 860, 200, 695, 314, 696, 102, 873, 853, 823, 76, 852, 606, 380, 302, 455, 479, 0, 870, 56, 120, 658, 7, 823, 62, 517, 979, 516, 184, 90, 264, 793, 425, 267, },
        {673, 340, 739, 394, 150, 312, 45, 759, 868, 11, 203, 227, 533, 443, 137, 592, 451, 153, 155, 235, 302, 959, 643, 666, 471, 597, 224, 320, 160, 495, 239, 536, 99, 347, 0, 673, 462, 940, 695, 153, 640, 155, 583, 488, 147, 634, 964, 623, 266, 871, },
        {296, 208, 233, 102, 141, 289, 913, 703, 461, 295, 476, 807, 381, 547, 495, 325, 411, 859, 368, 756, 86, 328, 93, 544, 244, 990, 379, 311, 566, 726, 560, 69, 360, 4, 360, 0, 387, 725, 309, 4, 678, 144, 634, 634, 72, 981, 249, 909, 789, 653, },
        {94, 244, 979, 760, 246, 544, 822, 597, 107, 599, 496, 61, 681, 711, 434, 990, 755, 124, 306, 555, 971, 665, 113, 393, 773, 517, 791, 60, 302, 541, 812, 175, 542, 952, 734, 507, 0, 167, 536, 283, 839, 681, 27, 850, 486, 996, 985, 794, 702, 33, },
        {584, 662, 188, 654, 828, 955, 76, 916, 98, 568, 22, 429, 43, 641, 845, 879, 926, 456, 50, 888, 358, 744, 477, 702, 499, 511, 611, 252, 708, 656, 931, 874, 402, 306, 618, 346, 839, 0, 841, 358, 66, 77, 855, 984, 347, 444, 350, 594, 581, 715, },
        {852, 536, 821, 288, 556, 532, 252, 978, 861, 625, 253, 555, 297, 753, 826, 540, 540, 282, 363, 232, 735, 99, 549, 586, 280, 868, 955, 779, 560, 243, 772, 547, 729, 211, 576, 697, 505, 479, 0, 120, 798, 791, 861, 721, 203, 97, 13, 229, 394, 343, },
        {912, 302, 634, 688, 614, 928, 477, 16, 167, 42, 788, 618, 347, 512, 290, 552, 910, 272, 405, 820, 43, 718, 745, 113, 337, 999, 6, 779, 11, 494, 578, 208, 17, 271, 74, 841, 547, 558, 17, 0, 913, 486, 435, 163, 882, 631, 292, 219, 182, 629, },
        {502, 265, 504, 603, 250, 639, 871, 59, 280, 330, 492, 894, 803, 646, 97, 863, 889, 186, 6, 383, 60, 931, 401, 635, 74, 989, 577, 459, 438, 348, 344, 972, 280, 688, 466, 860, 248, 886, 806, 421, 0, 562, 963, 256, 538, 22, 371, 656, 735, 88, },
        {168, 563, 846, 847, 551, 371, 516, 995, 605, 358, 690, 192, 503, 256, 486, 994, 182, 910, 538, 356, 920, 184, 372, 480, 123, 490, 445, 229, 549, 952, 46, 568, 520, 811, 643, 89, 553, 364, 11, 420, 903, 0, 139, 832, 527, 672, 364, 657, 622, 407, },
        {943, 808, 481, 506, 731, 445, 39, 152, 95, 696, 338, 760, 172, 774, 350, 700, 634, 507, 687, 509, 446, 966, 398, 343, 221, 98, 935, 45, 223, 488, 683, 184, 98, 514, 493, 240, 34, 427, 106, 421, 947, 882, 0, 674, 71, 931, 61, 150, 466, 398, },
        {761, 621, 670, 446, 304, 383, 106, 455, 812, 125, 256, 485, 207, 778, 964, 883, 301, 282, 830, 881, 553, 686, 183, 73, 372, 721, 232, 502, 309, 979, 357, 489, 762, 823, 625, 769, 100, 538, 667, 990, 497, 331, 614, 0, 339, 154, 473, 959, 485, 597, },
        {430, 175, 540, 157, 902, 864, 190, 861, 755, 213, 970, 76, 977, 146, 815, 993, 745, 890, 322, 560, 436, 863, 766, 893, 958, 195, 99, 381, 236, 678, 861, 93, 179, 225, 968, 666, 279, 766, 29, 718, 292, 539, 620, 892, 0, 285, 859, 766, 683, 190, },
        {148, 325, 663, 32, 560, 418, 245, 537, 675, 203, 900, 182, 931, 679, 601, 422, 222, 143, 819, 563, 277, 731, 262, 488, 317, 678, 579, 274, 118, 64, 300, 268, 653, 230, 532, 83, 284, 863, 109, 426, 906, 53, 587, 707, 85, 0, 182, 646, 883, 546, },
        {263, 294, 849, 839, 564, 319, 411, 57, 846, 659, 820, 215, 737, 694, 198, 919, 929, 477, 600, 798, 769, 80, 172, 947, 975, 327, 624, 477, 487, 264, 366, 835, 723, 318, 346, 370, 60, 221, 376, 241, 599, 690, 808, 632, 743, 128, 0, 279, 471, 499, },
        {157, 227, 883, 763, 563, 98, 307, 260, 626, 608, 849, 222, 762, 963, 43, 295, 679, 404, 201, 998, 749, 637, 226, 261, 859, 857, 479, 940, 460, 564, 289, 918, 256, 473, 422, 234, 641, 786, 694, 321, 361, 783, 828, 6, 633, 102, 847, 0, 223, 740, },
        {531, 769, 231, 443, 652, 599, 333, 89, 876, 895, 76, 998, 26, 952, 752, 337, 157, 443, 698, 639, 6, 159, 104, 992, 98, 530, 388, 776, 835, 523, 863, 427, 194, 52, 114, 218, 898, 382, 697, 474, 356, 132, 773, 979, 723, 138, 100, 670, 0, 659, },
        {654, 94, 896, 851, 572, 447, 19, 484, 407, 748, 60, 37, 35, 652, 159, 205, 536, 132, 998, 20, 409, 975, 153, 29, 907, 681, 55, 300, 217, 494, 66, 792, 748, 259, 417, 726, 15, 280, 95, 34, 320, 585, 8, 314, 731, 560, 180, 657, 681, 0, },
        };
        
    public class Dist implements Comparable
    {
        private int dist;
        private int index;
        
        public Dist(int dist, int index)
        {
            this.dist = dist;
            this.index = index;
        }
        
        public int compareTo( Object o )
        {
            Dist d = (Dist)o;
            return this.dist-d.dist;
        }

        public int getDist() {
            return dist;
        }
        
        public int getIndex() {
            return index;
        }
    }
    public static Dist [][] distOrd;
    /**
     * Crea un nou algorisme genčtic. 
     */
    public GA()
    {
        this.poblacions = new Vector();
        distOrd = new Dist[this.dist.length][];
        for( int i=0; i<dist.length; i++ )
        {
            distOrd[i] = new Dist[this.dist.length];
            for( int j=0; j<dist[i].length; j++ )
            {
                distOrd[i][j] = new Dist(dist[i][j],j);
            }
            java.util.Arrays.sort(distOrd[i]);
        }
    }
    
    public static double getFitness( Individu individu )
    {
        double fitness = 0;
        for( int i=0;i<individu.size(); i++ )
        {
            int ind1 = individu.getAt(i);
            int ind2 = individu.getAt((i+1)%individu.size());
            fitness += dist[ind1][ind2];
        }
        return fitness;
    }
    
    public void addPoblacio( Poblacio p )
    {
        this.poblacions.addElement(p);
    }
    
    public Individu novaGeneracio()
    {
        TreeSet millors = new TreeSet();
        Iterator it = this.poblacions.iterator();
        while( it.hasNext() )
        {
            Poblacio p = (Poblacio)it.next();
            millors.add(p.novaGeneracio());
        }
        if ( this.poblacions.size()>1 )
            this.migra();
        return (Individu)millors.first();
    }
    
    public void migra()
    {
        Random r = new Random();
        TreeSet millors = new TreeSet();
        Iterator it = this.poblacions.iterator();
        String sDesde = "";
        while( it.hasNext() )
        {
            Poblacio p = (Poblacio)it.next();
            if ( r.nextDouble()<p.getProbEmigracio() )
            {
                sDesde = p.getSNom() + ", "  + sDesde; 
                millors.addAll(p.getMillorsIndividus(2));
            }
        }
        if ( millors.size() > 0 )
        {
            it = this.poblacions.iterator();
            while( it.hasNext() )
            {
                Poblacio p = (Poblacio)it.next();
                if ( r.nextDouble()<p.getProbInmigracio() )
                {
                    p.afegeixIndividus(millors);
                    System.out.println("Migració des de " + sDesde + " cap a " + p.getSNom());
                }
            }
        }
    }
    
    public static int distancia( int i, int j )
    {
        return dist[i][j];
    }
    
    public void desastre()
    {
        Iterator it = this.poblacions.iterator();
        while( it.hasNext() )
        {
            Poblacio p = (Poblacio)it.next();
            p.desastre();
        }      
    }
}