TIPE voyageur de commerce-Algo génétique

[charliedecourchelle]

import random 
import numpy as np

def fact(n): #fonction factorielle
    if n!=0:
        return fact(n-1)*n
    else:
        return 1


def Fischer_Yates(G): #renvoie un cycle hamiltonien de G
    n=len(G)
    L=[i for i in range(n)]
    for k in range(1,n):
        j=random.randint(0,k)
        L[k], L[j] = L[j], L[k] #on permute deux élément entre eux
    L.append(L[0]) #on ferme avec le premier élément pour faire un cycle
    return L


def length_cycle(G, L): #renvoie le poid d'un cycle L de G
    a=0
    for i in range(len(L)-1):
        a+=G[L[i]][L[i+1]]
    return a


def population(G, i): #génère une population de i individus de G (individu=(poid, cycle))
    L=[]
    assert i <= fact(len(G)) 
    while len(L)!=i:
        a = Fischer_Yates(G)
        if (length_cycle(G,a),a) not in L:
            L.append((length_cycle(G,a),a))
    return L


def croisement(cycle1, cycle2): #croise deux cycles
   	 n = len(cycle1)
   	 cycle = cycle1[:n//2]
   	 for p in cycle2:
   	     if p not in cycle:
   	         cycle.append(p)
   	 return (length_cycle(G,cycle), cycle)
    
    
def mutation(pop, mutation_rate): #opère une mutation avec probabilité p sur chaque individus de pop
    for i in range(len(pop)):
        if np.random.random() < mutation_rate:
            j, k = np.random.choice(range(len(pop[i])), 2)
            pop[i][j], pop[i][k] = pop[i][k], pop[i][j]
    return pop
            
            
def selection(pop): #on ne garde que la moitié avec les poids les plus faibles
    pop.sort()
    pop=pop[:len(pop)//2]
    return pop


def algo_gene(i : int,L : list,q : float):# i=nombre d'itération voulue, L=population initiale, q=taux de mutation
    pop = selection(L) 
    fils = mutation([croisement(pop[2*i][1], pop[2*i+1][1]) for i in range(len(pop)//2)], q) #fils avec mutation issus de croisement
    pop += fils
    if i==1 :
        return(min(pop))
    else :
        return(algo_gene(i-1,pop,q))
        
[liste-des-gares.csv](https://github.com/mp-info/mp-info.github.io/files/10114145/liste-des-gares.csv)

[fortierq]

Peux-tu rappeler quelle était la question?

[charliedecourchelle]

Déjà mon mutation ne marche pas et je ne sais pas bien manipuler le module random donc j’aurais aimé avoir votre aide dessus et votre avis sur mon algorithme (optimisation ou autre). Merci beaucoup

…

Sent from my iPhone On 3 Dec 2022, at 11:52, Quentin Fortier ***@***.***> wrote:  Peux-tu rappeler quelle était la question? — Reply to this email directly, view it on GitHub<#3 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/A4PF3HQ4CMDAZH2JFYYP5F3WLMQ47ANCNFSM6AAAAAASOSIGYM>. You are receiving this because you authored the thread.Message ID: ***@***.***>

[fortierq]

Il manque des [1] dans mutation (tu stockes des couples (longueur, chemin) et il faut modifier le chemin) :

def mutation(pop, mutation_rate): #opère une mutation avec probabilité p sur chaque individus de pop
    for i in range(len(pop)):
        if np.random.random() < mutation_rate:
            j, k = np.random.choice(range(len(pop[i][1])), 2)
            pop[i][1][j], pop[i][1][k] = pop[i][1][k], pop[i][1][j]
    return pop

Remarque : ta population de cycles décroît strictement à chaque itération, car à partir de n cycles, tu en enlèves la moitié, ce qui en donne n/2, puis tu croise les n/2 cycles deux par deux, ce qui en ajoute n/4.
Donc tu passes de n cycles à 3n/4 à chaque itération.
Donc tu peux te retrouver avec 0 cycle avant le nombre d'itérations souhaitées (i).
A la place, tu peux croiser chaque cycle k avec le cycle k+1, de façon à générer n/2 nouveaux cycles par croisement.

[charliedecourchelle]

Super je vous remercie, en gros j’opère ma selection une fois les fils ajoutés à ma population et non des le départ ? Envoyé à partir de Courrier<https://go.microsoft.com/fwlink/?LinkId=550986> pour Windows De : Quentin ***@***.***> Envoyé le :samedi 3 décembre 2022 14:36 À : ***@***.***> Cc : ***@***.***>; ***@***.***> Objet :Re: [mp-info/mp-info.github.io] TIPE voyageur de commerce-Algo génétique (Discussion #3) Il manque des [1] dans mutation (tu stockes des couples (longueur, chemin) et il faut modifier le chemin) : def mutation(pop, mutation_rate): #opère une mutation avec probabilité p sur chaque individus de pop for i in range(len(pop)): if np.random.random() < mutation_rate: j, k = np.random.choice(range(len(pop[i][1])), 2) pop[i][1][j], pop[i][1][k] = pop[i][1][k], pop[i][1][j] return pop Remarque : ta population de cycles décroît strictement à chaque itération, car à partir de n cycles, tu en enlèves la moitié, ce qui en donne n/2, puis tu croise les n/2 cycles deux par deux, ce qui en ajoute n/4. Donc tu passes de n cycles à 3n/4 à chaque itération. Donc tu peux te retrouver avec 0 cycle avant le nombre d'itérations souhaitées (i). A la place, tu peux croiser chaque cycle k avec le cycle k+1, de façon à générer n/2 nouveaux cycles par croisement. — Reply to this email directly, view it on GitHub<#3 (reply in thread)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/A4PF3HWIN7AHOVASELYZOT3WLNEE7ANCNFSM6AAAAAASOSIGYM>. You are receiving this because you authored the thread.Message ID: ***@***.***>