Problem škatel

Če je lahko v eni škatli samo ena škatla potem je EA ful ful lažji. :)

Mogoče za trening ko mi bo dolgčas.

Graf vsebovanosti je lahko večkrat pretrgan. Več takih grafov vsebovanosti je v splošnem rešitev.

Rabiš dodatno informacijo, kje se kakšen začne in kje neha. To so rešitve in niso vse optimalne in v splošnem jih je več taboljših.

Skatle:
0:3 5 4
1:10 4 10
2:9 75 77
3:24 84 30
4:766 397 714
5:2315 9568 1202
6:434 398 4107
7:2842 566 2200
8:8254 9438 591
9:7 6 4

Resitev:
2/10
0->9 1->2 2->4 3->6 4->7 6->5 7->8 9->3 (notranja skatla->zunanja skatla)

Mislim da resitev stima. Ce najde kdo boljso resitev ali ugotovi da je resitev napacna naj pove nenadoma. :)

Bravo snow, bravo. Tko se dela.

Porabil sem nekje uro.
Če hočem zadevo naštimat na 500 škatel spremenim eno cifro.


2% hmm nevem. Tako sem nastavil začetno. Ti gruntaj in se igraj. :)
Pa lahko probuješ različne velikosti populacij - naštimaš v main funkciji ko narediš instanco.
Pa štimaš lahko tournament size (zdej je na 4... no cifra tam je 3 ker vedno vzame enega.. se pravi +1)
Lahko bi tud kak crossover si pogruntal :) Lahko ti dam ideje če hočeš.

//evolucijsko zlaganje skatlic - by snow
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>

struct SSkatla{
    int x;
    int y;
    int z;
    SSkatla(int, int, int);
};

SSkatla::SSkatla(int ix, int iy, int iz)
{
    x = ix;
    y = iy;
    z = iz;
}

struct SGenome{
    std::vector<int> zunanja;
    int fitness;
    SGenome(int);
};

SGenome::SGenome(int s)
{
    for(int i=0;i<s;i++)
    {
        zunanja.push_back(-1);
    }
}

class CGASkatle{
    std::vector<SSkatla> skatle;
    std::vector<SGenome> population;
    std::vector<SGenome> selected;
    int Fitness(SGenome&);
    
    int SkatliPasejo(SSkatla, SSkatla);
    
    int populationsize;
    int skatelsize;
    
    int bestfitness;
    int bestindex;
    
    int prevbest;
    
    public:
    CGASkatle(int, int);
    void Evaluation();
    void Selection();
    void Mutation();

};

CGASkatle::CGASkatle(int p, int s)
{
    srand(static_cast<unsigned int>(time(0)));
        
    populationsize=p;
    skatelsize=s;
    
    bestfitness=s;
    bestindex=0;
    
    prevbest=s;
    
    for(int i=0;i<populationsize;i++)
    {
        population.push_back(SGenome(skatelsize));
        selected.push_back(SGenome(skatelsize));
    }
    
    //zmisli si nekaj random velikih skatlic :)
    int max=1000;
    for(int j=0;j<skatelsize;j++)
    {
        max=static_cast<int>(pow(10,1+rand()%4));
        skatle.push_back(SSkatla(1+rand()%max,1+rand()%max,1+rand()%max));
        std::cout<<j<<":"<<skatle[j].x<<" "<<skatle[j].y<<" "<<skatle[j].z<<" "<<std::endl;
    }
}

int CGASkatle::SkatliPasejo(SSkatla zunaj, SSkatla notri)
{
    if(zunaj.x>notri.x && zunaj.y>notri.y && zunaj.z>notri.z){return 1;}
    if(zunaj.x>notri.x && zunaj.y>notri.z && zunaj.z>notri.y){return 1;}
    if(zunaj.x>notri.y && zunaj.y>notri.x && zunaj.z>notri.z){return 1;}
    if(zunaj.x>notri.y && zunaj.y>notri.z && zunaj.z>notri.x){return 1;}
    if(zunaj.x>notri.z && zunaj.y>notri.x && zunaj.z>notri.y){return 1;}
    if(zunaj.x>notri.z && zunaj.y>notri.y && zunaj.z>notri.x){return 1;}
    
    return 0;
}

//prešteje vidne škatle (odšteje škatle v škatlah od vseh)
int CGASkatle::Fitness(SGenome& res)
{
    int f=skatelsize;
    
    for(int c=0;c<skatelsize;c++)
    {
        if(res.zunanja[c]!=-1)
        {
            f--;
        }
    }
    
    return f;
}

//našima fitness vsem in si zapomni najboljšega
void CGASkatle::Evaluation()
{
    for(int i=0;i<populationsize;i++)
    {
        population[i].fitness=Fitness(population[i]);
        if(population[i].fitness<bestfitness)
        {
            bestfitness=population[i].fitness;
            bestindex=i;
        }
    }
    
    if(prevbest!=bestfitness)
    {
        prevbest=bestfitness;
        std::cout<<std::endl<<bestfitness<<"/"<<skatelsize<<std::endl;
        /*
        for(int j=0;j<skatelsize;j++)
        {
            if(population[bestindex].zunanja[j]!=-1)
            {
                std::cout<<j<<"->"<<population[bestindex].zunanja[j]<<" ";
            }
        }
        */
    }
}

//tournament selekcija... tournament size 4.
void CGASkatle::Selection()
{
    for(int i=0;i<populationsize;i++)
    {
        int bidx=rand()%populationsize;
        int bf=population[bidx].fitness;
        int tsize=3;
        while(tsize--)
        {
            int opp=rand()%populationsize;
            if(population[opp].fitness<bf)
            {
                bf=population[opp].fitness;
                bidx=opp;
            }
        }
        selected[i]=population[bidx];
    }
    population.swap(selected);
}

void CGASkatle::Mutation()
{
    for(int p=0;p<populationsize;p++)
    {
        for(int s=0;s<skatelsize;s++)
        {
            //verjetnost mutacije je 20/1000
            if(rand()%1000<=20)
            {
                int v=rand()%skatelsize;
                if(SkatliPasejo(skatle[v],skatle[s]))
                {
                    for(int d=0;d<skatelsize;d++)
                    {
                        if(population[p].zunanja[d]==v)
                        {
                            population[p].zunanja[d]=-1;
                        }
                    }
                    population[p].zunanja[s]=v;
                }
            }
        }
    }    
}

int main()
{    
    // (populationsize, skatel)
    CGASkatle solver(200,500);
    while(1)
    {
        solver.Selection();
        solver.Mutation();
        solver.Evaluation();
    }

    return 0;
}

To je danes poslal profesor na vprašanje ali so lahko dve vzporedni škatli v eni škatli:

"To je težja različica naloge. Načeloma bi lahko v neko škatlo 'vzporedno' shranili več škatel. Zopet se lahko sam odločite, katero nalogo boste reševal."


Snow: hvala. Mogoče bom uporabil.

Napiši program, pa si zmislimo 500 škatel pa gremo testirat.

od kje si pa te omejitve dobil?

Naloga
Danih je n (500) škatlic znanih velikosti ( ai, bi, ci), i = 1,..., n.
Sestavi program, ki bo določil, kako naj zložimo škatlice ene v druge, tako da bo na koncu ostalo vidnih čim manj škatlic.
Namig: pomagaj si z grafom vsebovanosti škatlic.

**Naša naloga je postaviti škatle ene v drugo tako, da bo vidnih čim manj škatlic. Število škatel, katerim se ne bi uspelo uvrstiti v množici mora biti minimalno**

Jaz sem razumel takole:torej število škatel, katerim se nebi uspelo uvrstiti v množici (v pakiranje?) more biti minimalno..
torej kao pakiramo enkrat, ostale škatle ki so preostale, jih pač pustimo kukr so, sam more jih bit minimalno?

Primer:
mamo 5 škatel in recimo da
1-> 2 ->3 to potem izgleda od zunaj kot ena škatla (kot trojka)
Preostaneta 4 in 5, a vendar tudi če 4 ->5 jih pustimo vsako posebej?
Kao to so te škatle, k se niso uspele uvrstit v pakiranje 1->2->3,
torej v našem primeru je sta te škatli 2.
Lahko bi pakirali tudi večrat, recimo 4->5 (poleg 1-2-3) in potem imeli od zunaj le 2 škatle?

mia- a tvoja rešitev z matriko vsebovanosti deluje za oba problema?

To mi je všeč pri EA.. se da dokaj hitro poštimat za kakšne variante.
Tudi za ono težjo varianto če bi lahko v eno škatlo dal več škatel vzporedno. Ampak tam ne vem kako bi preverjal ali dve škatli pašejo v eno? A za to obstajajo kakšne točne rešitve?

Mislim, da moraš potem preostale škatle prav tako pospraviti. Se pravi da imaš več urejevalnih postopkov.

Jim ne potegne tale EA, a snow?

Snow: malo več potrpljenja. Delal bom tvojo verzijo. In če se mi bo dalo še drugo verzijo.