[Python] Genetic algorithm?

[Che]

Detalii:

Am mai multe liste de liste dupa cum urmeaza:

lista_A = [[1, 5, 15, 25,...n],

                [23, 25, 27,...p]...]

lista_B = # asemanatoare cu lista_A dar nu identica

lista_C = # asemanatoare cu cele de mai sus

lista_D, lista_E, [...] lista_Z si apoi lista_AB... si tot asa, in total 355 de liste de liste.

 

Listele de liste au toate aceeasi lungime dar elementele nu sunt egale ca lungime nici in cadrul aceleasi liste si nici ca pozititie de la o lista la alta, mai exact:

len(lista_A)=len(lista_B)=len(lista_C)=len(lista...)[...] etc.

Dar, len(lista_A[0]) != len(lista_A[1]) != len(lista_A[2]) !=...etc.

dar si:

len(lista_A[0]) != len(lista_B[0]) != len(lista_C[0])... etc. la fel si pentru al doilea elemnt si al treilea s.a.m.d.

 

In afara de toate aceste liste, mai este o lista de liste numita matrita dupa cum urmeaza:

matrita = [[1, 2, 3, 18, 50,..., 70, 95],

                 [23, 35, 45, 55, 68,..., 89, 100]... n]

len(matrita) = len(lista_A) = len(lista_B) = len(lista_C)...etc.

si

len(matrita[0]) = len(matrita[1]) = len(matrita[2]) = len(matrita[3]) etc. # toate elementele din amtrita au aceeasi lungime fixa de 30.

dar:

len(matrita[0]) != len(lista_A[0]) etc. elementele din fiecare lista de liste pot fi sau nu pot fi egale ca lungime cu cele din matrita.

 

Sumar:

Toate elementele din matrita au lungime fixa de 30. Fiecare element din toate celelalte liste de liste pot fi egale cu 30 ca lungime sau pot fi mai scurte, cu lungime de 0 (empty list), 1, 2,3 sau mai lungi.

Toate elementele, atat din listele de liste, cat si din matrita, sunt de tip int, ordonate crescator, nu sunt neaparat consecutive si iau valori de la 1 la 100 si doar din matrita au lungime egala.

Toate listele de liste, inclusiv lista de liste numita matrita, au toate aceeasi lungime fixa de 1000 de elemente (liste).

 

Fiecare lista de liste trebuie sa "marcheze" cat mai multe numere per item din matrita.

Am doua metode de calcul a performantei, dupa cum urmeaza, si dau ca exemplu doar o singura lista de liste:

# varianta 1: atunci cand nu conteaza numarul de numere al fiecarui item din lista de liste marcat in matrita:

performanta_totala = 0.0

temp_performance = []

for i in range(len(matrita)):

     matched_perf = len(lista_A[i])/len(sorted(list(set(matrita[i]).intersection(lista[i]))))

     temp_performance.append(matched_perf)

performanta_totala = sum(temp_performance)/len(temp_performance)



# varianta 2: atunci cand matched trebuie sa fie minim 8 altfel se considera eroare sau zero:

performanta_totala = 0.0

temp_performance = []

for i in range(len(matrita)):

     matched_perf = 0.0

     # trebuie sa faca match la minim 8 sau mai multe, altfel este zero:

     if len(lista_A[i]) >=8:

          if len(sorted(list(set(matrita[i]).intersection(lista[i])))) >=8:

                matched_perf = len(lista_A[i])/len(sorted(list(set(matrita[i]).intersection(lista[i]))))

     temp_performance.append(matched_perf)

performanta_totala = sum(temp_performance)/len(temp_performance)

 

Cum am zis si mai sus, asta este doar pentru a verifica performanta totala doar in cazul unei singure liste de liste.

Acum, am inteles ca metoda .intersection_update() poate lua doua sau mai multe liste si sa dea ca rezultat doar numerele comune din toate listele.

Eu vreau sa gasesc combinatia de liste de liste cu cea mai mare performanta toatala (si pentru varianta 1 dar si pentru varianta 2 cand trebuie sa fie de la 8 in sus).

Pentru asta m-am gandit sa pun intr-o lista toate listele de liste ca de exemplu:

all_lists = [lista_A, lista_B, lista_C...]

si sa fac ceva de genul:

for cmb in combinations(all_lists, 2):

 si apoi cu intersection_update sa verific performanta totala a fiecarei combinatii de cate doua liste. Apoi de cate 3 liste si tot asa. Ideea este sa gasesc cea mai buna combinatie de liste de liste care sa aiba cea mai mare performanta toatala si aceasta sa fie mai mare decat performanta totala a oricarei liste luate individual.

Probleme:

1. Nu stiu cat de mare ar trebui sa fie cmb, poate fi de 2 sau de 1 dar poate fi si de 20, 30, 50 ???
2. Mai este si varianta nu doar cu intersection_update ci sa fie ceva de genul sum (adica doua sau mai multe elemente din liste diferite luate impreuna gen lista_A[0] + lista_B[0]) sau diferenta dintre doua sai mai multe, gen lista_A[0] = [x for x in lista_A[0] if x not in lista_B[0]] sau combinatii dintre intesection si sum sau dintre diferente si sum sau dintre toate cele trei. Nu stiu care ar putea fi cea mai buna configuratie.

 

Cum as putea rezolva aceasta problema?

Ma gandeam ca toata aceasta chestie s-ar putea rezolva simplu si frumos cu un algoritm genetic. Aveti o alta idee?

Problema este ca nu am habar deloc cum ar trebui sa arate un astfel de algoritm genetic. Am cautat pe Google, am vazut si pe Yotube si am si citit diferite articole dar tot mi se pare ca greu de implementat in aceasta situatie.

Ma puteti ajuta, va rog?

 

Mutumesc mult de tot!

Edited August 24, 2022 by Che
Adaugare fragment de cod sursa usor modificat.