• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Algorytm genetyczny słabo działa

VPS Starter Arubacloud
+1 głos
151 wizyt
pytanie zadane 24 kwietnia 2017 w C# przez Adam Olesiak Gaduła (3,290 p.)
edycja 24 kwietnia 2017 przez Adam Olesiak

Hej!

Mam taki projekt, o którym słyszałem na sucho na uczelni na tzw. wstępie do informatyki i trochę mnie to zaciekawiło, ale niestety po napisaniu go mam dosyć marne rezultaty, także jak ktoś ma ochotę, to proszę o wsparcie ;)

Zadanie:

Znajdź trzy sinusy, które po zsumowaniu będą "jak najbliżej" listy punktów(x,y) podanych jako argument do programu.

 

Mój program:

Każdy sinus zapisałem w takiej postaci a*sin(b*x+c)+d, gdzie a,b,c,d to zmienne typu double, które będę próbował dobrać.

Jest jeszcze klasa Creature, która po prostu zawiera trzy sinusy i zmienną double rating która jest sumą odległości y punktów od funkcji w punkcie x. - Zmienna potrzebna do sortowania.

 

Pętla główna programu:

//sw - instancja stopwatch, do mierzenia czasu, aby nie spamować konsoli
//population - tablica Creature
//vec - tablica wektorów 2d określająca punkty do których chcę się zbliżyć

do
            {
                rateCreatures(population, vec);//wyznacza ratio dla każdego
                bestRatio = sortCreatures(population);//sortuje i zwraca wartość pierwszego po posortowaniu

                timeSinceLastLog = sw.Elapsed.Seconds;
                if (timeSinceLastLog > 1f)
                {
                    Console.WriteLine("Iteration: " + iter);
                    Console.WriteLine("current best creature ratio: " + bestRatio);
                    Console.WriteLine("current average creature ratio: " + getAvgRate(population)+"\n");
                    timeSinceLastLog = 0;
                    sw.Restart();
                }

                replaceHalfCreatures(population, random, range);//zostawia 0-50%, dla 50%-95% wybiera dwa losowe Creature z najlepszej połowy i kopiuje po koleji argumenty(rzuca monetą żeby sprawdzić z którego rodzica wziąć dany argument), dla 95%-100% nadpisuje nową, zupełnie losową instancją Creature
                iter++;
            } while (true);

Co do losowania argumentów przy tworzeniu nowych, losowych instancji Creature i zawierających Sinusów, to mam zmienną double range, którą ręcznie ustawiam, np na 10 - wtedy wszystkie typy wartościowe są losowane od -10 do 10. Zmienianie nie pomaga za bardzo - próbowałem

 

Na koniec załączam całość kodu:(projekt na 2h, więc nie jest piknie, ale komentarze co do jakości kodu, albo dobrych praktyk programowania też mile widziane! ;))

Klasa Sinus:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GeneticAlgorithm
{
    class Sinus
    {
        public double a, b, c;

        public Sinus(Random rand, double range)
        {
            //default: make a random Sinus object

            a = (rand.NextDouble() - 0.5f) * range*2f;
            b = (rand.NextDouble() - 0.5f) * range*2f;
            c = (rand.NextDouble() - 0.5f) * range*2f;
        }

        public Sinus(double _a, double _b, double _c)
        {
            //used for parenting in creature func.
            a = _a;
            b = _b;
            c = _c;
        }
    }
}

Klasa Creature:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace GeneticAlgorithm
{
    class Creature
    {
        public Sinus s1, s2, s3;
        public double d;
        public double rating;


        public Creature(Random rand, double range)
        {
            //default: for first generation only
            s1 = new Sinus(rand, range);
            s2 = new Sinus(rand, range);
            s3 = new Sinus(rand, range);
            d = (rand.NextDouble() - 0.5f) * 200f;
        }

        public void replace(Creature parent1, Creature parent2, Random rand, double range)
        {

            //data to fill and use to make new dude
            Sinus sin1 = new Sinus(rand, range);
            Sinus sin2 = new Sinus(rand, range);
            Sinus sin3 = new Sinus(rand, range);
            double d1=0;

            for (int i=0;i<10;i++)
            {
                int coinFlip = rand.Next(2);
                bool useFirst = true;
                if (coinFlip == 1)
                    useFirst = false;

                switch(i)
                {
                    case 0:
                        sin1.a = (useFirst) ? parent1.s1.a : parent2.s1.a;
                        break;
                    case 1:
                        sin1.b = (useFirst) ? parent1.s1.b : parent2.s1.b;
                        break;
                    case 2:
                        sin1.c = (useFirst) ? parent1.s1.c : parent2.s1.c;
                        break;

                    case 3:
                        sin2.a = (useFirst) ? parent1.s2.a : parent2.s2.a;
                        break;
                    case 4:
                        sin2.b = (useFirst) ? parent1.s2.b : parent2.s2.b;
                        break;
                    case 5:
                        sin2.c = (useFirst) ? parent1.s2.c : parent2.s2.c;
                        break;

                    case 6:
                        sin3.a = (useFirst) ? parent1.s3.a : parent2.s3.a;
                        break;
                    case 7:
                        sin3.b = (useFirst) ? parent1.s3.b : parent2.s3.b;
                        break;
                    case 8:
                        sin3.c = (useFirst) ? parent1.s3.c : parent2.s3.c;
                        break;

                    case 9:
                        d1 = (useFirst) ? parent1.d : parent2.d;
                        break;
                }
                s1 = sin1;
                s2 = sin2;
                s3 = sin3;
                d = d1;
            }
        }

        public void rate(Vector2[] points)
        {
            double toReturn = 0;
            for(int i=0; i < points.Length; i++)
            {
                double x = points[i].x;
                double y = points[i].y;
                double fY = this.valueIn(x);

                toReturn += Math.Sqrt((y - fY) * (y - fY));//TODO: consider getting rid of sqrt - may be more efficient
            }
            rating = toReturn;
        }

        public double valueIn(double x)
        {
            return Math.Sin(x * s1.a + s1.b) * s1.c + Math.Sin(x * s2.a + s2.b) * s2.c + Math.Sin(x * s3.a + s3.b) * s3.c + d;
        }
    }
}

Klasa Program:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace GeneticAlgorithm
{
    public struct Vector2
    {
        public double x, y;
    }


    class Program
    {
        static void Main(string[] args)
        {
            double range = 1f;
            Vector2[] vec = new Vector2[5];
            vec[0].x = 0f;
            vec[0].y = 5f;
            vec[1].x = 1f;
            vec[1].y = 3f;
            vec[2].x = 2f;
            vec[2].y = -5f;
            vec[3].x = 3f;
            vec[3].y = 3f;
            vec[4].x = 4f;
            vec[4].y = 0f;


            Random random = new Random();
            const int populationSize = 200;
            Creature[] population;
            List<Creature> creatures = new List<Creature>();

            for (int i = 0; i < populationSize; i++)
                creatures.Add(new Creature(random, range));
            population = creatures.ToArray();

            int iter = 0;
            double bestRatio = 0;
            float timeSinceLastLog = 1f;

            Stopwatch sw = Stopwatch.StartNew();

            rateCreatures(population, vec);
            Console.WriteLine("Iteration: " + 0);
            Console.WriteLine("current best creature ratio: " + sortCreatures(population));
            Console.WriteLine("current average creature ratio: " + getAvgRate(population) + "\n");

            do
            {
                rateCreatures(population, vec);
                bestRatio = sortCreatures(population);

                timeSinceLastLog = sw.Elapsed.Seconds;
                if (timeSinceLastLog > 1f)
                {
                    Console.WriteLine("Iteration: " + iter);
                    Console.WriteLine("current best creature ratio: " + bestRatio);
                    Console.WriteLine("current average creature ratio: " + getAvgRate(population)+"\n");
                    timeSinceLastLog = 0;
                    sw.Restart();
                }

                replaceHalfCreatures(population, random, range);
                iter++;
            } while (population[0].rating > 10f);

        }

        static void rateCreatures(Creature[] population, Vector2[] points)
        {
            foreach (Creature c in population)
                c.rate(points);
        }

        static double sortCreatures(Creature[] population)
        {
            population = population.OrderBy(n => n.rating).ToArray();
            /*Console.WriteLine("first: " + population[0].rating);
            Console.WriteLine("second: " + population[1].rating);
            Console.WriteLine("last: " + population[199].rating);*/

            return population[0].rating;
        }

        static void replaceHalfCreatures(Creature[] population, Random rand, double range)
        {
            int creaturesToKill = population.Length / 2;

            for(int i = creaturesToKill - 1; i<population.Length; i++)
            {
                if (i < population.Length - 10)
                {
                    //find two random creatures of the better part(TODO: the higher they are, the more likely should they be to be picked for gene selection)
                    int parent1Index = rand.Next(creaturesToKill);
                    int parent2Index = rand.Next(creaturesToKill);

                    population[i].replace(population[parent1Index], population[parent2Index], rand, range);
                }
                else
                {
                    population[i] = new Creature(rand, range);
                }
            }
        }

        static double getAvgRate(Creature[] population)
        {
            double toReturn = 0;
            foreach (Creature c in population)
                toReturn += c.rating;
            return toReturn / population.Length;
        }
    }
}

 

Na koniec to co widać na konsoli:

Iteration: 0
current best creature ratio: 19,8839451514098
current average creature ratio: 378,409788452106

Iteration: 4330
current best creature ratio: 19,8839451514098
current average creature ratio: 342,072062725768

Iteration: 8751
current best creature ratio: 19,7690783591971
current average creature ratio: 346,062072233154

Iteration: 13241
current best creature ratio: 19,6651993027145
current average creature ratio: 353,915512082182

Iteration: 17643
current best creature ratio: 19,8839451514098
current average creature ratio: 326,881308248833

Iteration: 22078
current best creature ratio: 18,7688923014568
current average creature ratio: 346,773040628046

Iteration: 26373
current best creature ratio: 19,3618102124538
current average creature ratio: 342,846981933711

1 odpowiedź

0 głosów
odpowiedź 24 kwietnia 2017 przez adrian17 Ekspert (344,100 p.)
`replaceHalfCreatures` jest źle napisane. Zabij N (np. 10 lub 10%, eksperymentuj) najgorszych, resztę skrzyżuj.
komentarz 24 kwietnia 2017 przez Adam Olesiak Gaduła (3,290 p.)

Jak tak zrobię, to bardzo dobrze wpływa na "average ratio" - więc cała populacja staje się bardziej dostosowana do zadania, ale samo "best ratio" jest bardzo słabe - zgaduję, że dlatego że jak już otrzymamy dobry egzemplarz, to zamiast go zostawić, aby przekazywał dalej geny, to jest od razu nadpisywany przez krzyżowanie.

 

Przed zmianą:

new best creature: 0th iteration: 11,8468436591165
new best creature: 10th iteration: 11,5455694663819
new best creature: 272th iteration: 11,4382025029851
new best creature: 791th iteration: 11,4254453270505
new best creature: 871th iteration: 10,7335655800079
new best creature: 77790th iteration: 10,5456657499788

 

Po zmianie:

new best creature: 0th iteration: 12,3140892204387
new best creature: 1th iteration: 11,7240352612209
new best creature: 4th iteration: 11,6632079779688
new best creature: 5th iteration: 11,6488319344211
new best creature: 7th iteration: 11,4805742472307
new best creature: 9th iteration: 11,4490666557418
new best creature: 16th iteration: 11,4152684554633
new best creature: 375th iteration: 11,1314711866455
new best creature: 27925th iteration: 11,0039443664342
new best creature: 48763th iteration: 10,9808590834986

 

Za to Average ratio po zmianie: 0-wa iteracja ~250, 1000-na iteracja ~25

przed zmianą: 0-wa iteracja ~250, 100-na iteracja ~250

 

 

Nowa funkcja replaceHalfCreatures:

static void replaceHalfCreatures(Creature[] population, Random rand, double range)
        {
            int creaturesToKill = population.Length / 2;
            Stack<Creature> newHalf = new Stack<Creature>();
            for (int i = creaturesToKill; i < population.Length; i++) //próbowałem iterować od i=0, i=5
            {
                if (i < population.Length - 10)
                {
                    //find two random creatures of the better part
                    int parent1Index = rand.Next(i);// próbowałe rand.Next(creaturesToKill);
                    int parent2Index = rand.Next(i);

                    //make a new object based on those two parents
                    newHalf.Push(Creature.reproduce(population[parent1Index], population[parent2Index], rand, range));//najpierw twórz obiekty, dopiero potem je wdrażaj, żeby dzieci nie robiły nowych dzieci w jednej generacji
                }
                else
                {
                    newHalf.Push(new Creature(rand, range));//najgorsze 10 egzemplarzy usuń i zastąp losowymi
                }
            }
            for (int i = creaturesToKill; i < population.Length; i++)
            {
                    population[i] = newHalf.Pop();//zastąp orginalne nowo stworzonymi
            }
        }

 

Podobne pytania

0 głosów
2 odpowiedzi 1,222 wizyt
pytanie zadane 29 listopada 2016 w C# przez Macek Kolo Mądrala (5,480 p.)
+1 głos
0 odpowiedzi 718 wizyt
0 głosów
4 odpowiedzi 1,795 wizyt

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...