AlgorytmGenetyczny.cs 3.62 KB
Newer Older
1 2 3 4 5 6 7
using System;

namespace nHetmanowGenetycznie
{
    public abstract class AlgorytmGenetyczny<TypOsobnika>
    {
        protected abstract TypOsobnika[] LosowaPopulacja(int rozmiar);
8
        protected abstract int Koniec(bool bestPossible, float[] przystosowanie);
9
        protected abstract float Przystosowanie(TypOsobnika osobnik);
10 11 12 13

        protected abstract void Krzyzuj(TypOsobnika osobnik1, TypOsobnika osobnik2, out TypOsobnika nowyOsobnik1,
            out TypOsobnika nowyOsobnik2);

14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
        protected abstract TypOsobnika Mutacja(TypOsobnika osobnik);

        protected int RozmiarPopulacji { get; set; }
        protected float PrawdopodobienstwoMutacji { get; set; }


        public TypOsobnika Szukaj(int liczbaIteracji)
        {
            TypOsobnika[] populacja = LosowaPopulacja(RozmiarPopulacji);
            float[] przystosowanie = new float[RozmiarPopulacji];
            int[] rodzice = new int[RozmiarPopulacji];

            while (liczbaIteracji > 0)
            {
                for (int i = 0; i < RozmiarPopulacji; i++)
                    przystosowanie[i] = Przystosowanie(populacja[i]);
30 31 32 33
 
                int wynik = Koniec(false, przystosowanie);
                if (wynik != -1)
                    return populacja[wynik];
34 35 36 37 38 39 40 41 42 43 44 45 46

                LosowanieDoKrzyzowania(przystosowanie, rodzice);
                TypOsobnika[] nowaPopulacja = new TypOsobnika[RozmiarPopulacji];
                for (int i = 0; i < rodzice.Length; i += 2)
                    Krzyzuj(populacja[rodzice[i]], populacja[rodzice[i + 1]],
                        out nowaPopulacja[i], out nowaPopulacja[i + 1]);

                for (int i = 0; i < nowaPopulacja.Length; i++)
                    nowaPopulacja[i] = Mutacja(nowaPopulacja[i]);

                populacja = nowaPopulacja;
                liczbaIteracji--;
            }
47

48 49
            for (int i = 0; i < RozmiarPopulacji; i++)//ponieważ nowaPopulacja nie posiada wyznaczonego przystosowania
                przystosowanie[i] = Przystosowanie(populacja[i]);
50
            Console.WriteLine("Nie znaleziono rozwiązania - wyświetlę najlepsze!");
51
            
52
            return populacja[Koniec(true, przystosowanie)];
53 54 55 56 57 58
        }

        void LosowanieDoKrzyzowania(float[] przystosowanie, int[] rodzice)
        {
            Random r = new Random();
            float[] progi = Progi(przystosowanie);
59 60
            var iloscElementow = przystosowanie.Length;
            for (int i = 0; i < iloscElementow - 1; i++)
61
            {
62 63
                rodzice[i] = Indeks((float) r.NextDouble(), progi);
                int liczbaIteracji = 100;
64
                do
65 66 67 68
                {
                    rodzice[i + 1] = Indeks((float) r.NextDouble(), progi);
                    liczbaIteracji--;
                } while (rodzice[i] == rodzice[i + 1] && liczbaIteracji > 0);
69
            }
70
        }
71 72 73 74 75 76 77 78 79 80

        private float[] Progi(float[] przystosowanie)
        {
            float[] progi = new float[przystosowanie.Length];
            float suma = 0;
            for (int i = 0; i < progi.Length; i++)
            {
                suma += przystosowanie[i];
                progi[i] = suma;
            }
81

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
            for (int i = 0; i < progi.Length; i++)
                progi[i] /= suma;
            return progi;
        }

        private int Indeks(float x, float[] progi)
        {
            int a = 0, b = progi.Length - 1;
            do
            {
                int c = (a + b) / 2;
                if (c == a)
                    return c;
                if (progi[c] >= x)
                    b = c;
                else
                    a = c;
            } while (a < b);
100

101 102 103 104
            return a;
        }
    }
}