Nessun miglioramento rispetto al passato.
Io parlo di
COMPRESSIONE NUMERICA , l'equivalente del winzip per un integrale numerico.
Usarlo o meno per il lotto
DEVE essere una scelta personale ,
non criticabile.
Aggiungo il listato, non sono riuscito ad allegarlo correttamente prima
#include<iostream.h> // Header file for receiving input and generating output.
#include<stdlib.h> // Header file containing C++ standard libraries.
#include<iomanip.h> // Header file for manipulating output.
#include<fstream.h> // Header file for using files.
#include<time.h> // Header file for calculating iteration times.
#include<math.h> // Header file for mathematical functions.
#include<stl.h> // Header file for Standard Template Library (STLs) <set, multiset>.
// Fitness of playing set is given by: fitness = # vertices dominated by candidate
# vertices in graph = `(m; n; k)
long double fact (const int &);
long int round (const long double);
bool ValidTicket (const short int *, const short int &, const short int &);
// Compute the factorial of n (i.e. n!).
long double fact (const int &n) f if (n < 2) return 1; // Stop recursion.
else return n * fact(n - 1); // (n > 1).
g// Rounds a number off to the nearest integer to avoid possible numerical truncation errors.
long int round (const long double n) f long int flrnum = (long int)floor(n);
if (n - flrnum < 0.5) return flrnum;
else return (long int)ceil(n); // (n - flrnum >= 0.5)
g// Determine whether a ticket (n-set) is valid (ticket contains no double numbers).
bool ValidTicket(short int *ticket, const short int &m, const short int &n) f multiset<short int, less<short int> > index;
multiset<short int, less<short int> >::iterator i;
for (short int counter = 0;counter < n;counter++) f index.insert(ticket[counter]); // Add number to index.
if (index.count(ticket[counter]) > 1) return false; // Ticket is invalid.
gi
= index.begin(); // Arrange ticket elements lexicographically.
for (short int counter = 0;i != index.end();ticket[counter++] = *i++);
return true; // Ticket is valid.
gint main () f short int m, n, k, L, p = 1, cMutate = 1, gMutate = 1; // Parameters for the lottery <m,n;k>, playing set size (L),
population size (p), candidate mutate size (cMutate < p), mutate set size (gMutate < L).
long int t, gen, iter=1; // Time limit (t), generation limit (gen), number of iterations on the same parameters (iter).
cout << endl << \nt GENETIC ALGORITHM (GA)" << endl;
cout << \Please specify the following parameters for the lottery hm,n;ki:" << endl;
cout << \m = "; cin >> m;
cout << \n = "; cin >> n;
cout << \k = "; cin >> k;
// If the user specified invalid lottery parameters.
if ((n > m-1) || (k > n-1) || (m < 3) || (n < 2) || (k < 1)) f cout << endl << \Invalid lottery parameters entered." << endl;
return 0; // Exit program.
gconst long int NumTickets = round(fact(m)/(fact(n)*(fact(m-n))));
cout << endl << \The order of the lottery graph Gh" << m << \," << n << \;" << k << \i is " << NumTickets << \." << endl;
cout << endl << \Please specify the following GA parameters:" << endl;
cout << \Playing set size = "; cin >> L;
do f if (gMutate >= L)
cout << \Mutation set size must be strictly less than the playing set size (" << L << \)." << endl;
cout << \gMutation set size = "; cin >> gMutate;
g while (gMutate >= L);
while (floor(p/2) < ((double)p/2)) f cout << \Population size = "; cin >> p;
if (floor(p/2) < ((double)p/2)) cout << \Population size needs to be a multiple of 2." << endl;
gdo f if (cMutate >= p)
cout << \# of candidates to mutate per generation must be strictly less than the population size (" << p << \)." << endl;
cout << \cMutation set size = "; cin >> cMutate;
g while (cMutate >= p);
cout << \Generation limit = "; cin >> gen; cout << \Time limit (in sec) = "; cin >> t;
// If the user specified invalid GA parameters.
if ((L < 2) || (L > (NumTickets-1)) || (p < 2) || (gen < 2) || (t < 2) || (cMutate < 1) ||
(gMutate < 1) || (iter < 1)) f cout << endl << ``Invalid GA parameters." << endl; return 0; // Exit program.
gshort int Population[p][L][n], TempInt, CurrentNumber = n, CurTicket[n], dcounter, tcounter, Intersect = 0,
candidate1, candidate2; // A GA population (of size p) consisting of playing sets (of size L).
oat GAPopFit[p], selection, ccandidate, fitnessmin, fitnessavg, fitnessmax; // Vector for storing fitness of candidate
playing sets (GAPopFit), values used for determining crossover partners (fitnesssum, selection, ccandidate), generation
minimum fitness (fitnessmin), generation average fitness (fitnessavg), generation maximum fitness (fitnessmax).
time t StartTime; // Trace execution time.
long int NumDominated, fitnesssum, UniquelyDominated[p+1][L], curgen = 0, NewFitness[L];
set<short int> CrossoverIndex, CrossoverGenes; // (Integrity) Check for crossover procedure (CrossoverIndex), check genes
used during crossover procedure (CrossoverGenes).
struct Fitness f long int fitness; // Fitness of generation candidate (given by the number of dominated vertices.
bool used, changed; // Candidate has been used and/or changed for crossover during a previous crossover procedure.
short int number; // Generation candidate indentification number.
Fitness *next; // Pointer to next fitness information of nextcandidate in linked-list.
g;
Fitness *FitnessList = new Fitness, *TempFitness, *TempFitness2;
fstream GAFitnessFile(\GAFitness.txt", ios::out); // Open \GAFitness.txt" for output of GA fitness information.
if (!GAFitnessFile) f // Check whether the file \GAFitness.txt" could be opened.
A.7. Intelligent genetic algorithm (Algorithm 7) 169
cerr << \The le n\GAFitness.txtn" could not be opened." << endl;
exit(1); // Exit program.
gfstream GAPopulationFile(\GAPopulation.txt", ios::out); // Open \GAPopulation.txt" for output of GA population info.
if (!GAPopulationFile) f // Check whether the file \GAPopulation.txt" could be opened.
cerr << \The le n\GAPopulation.txtn" could not be opened." << endl;
exit(1); // Exit program.
gGAPopulationFile << \GA for h" << setw(2) << m << `,' << setw(2) << n << `;' << setw(2) << k << \i :" << endl;
GAFitnessFile << \GA for h" << setw(2) << m << `,' << setw(2) << n << `;' << setw(2) << k << \i :" << endl << endl;
cerr << endl << \Initialising GA with " << p << \ random playing set candidates, please wait. . . ";
GAFitnessFile << \GA Parameters:" << endl
<< \Playing set size = " << setw(5) << L << endl
<< \gMutation set size = " << setw(5) << gMutate << endl
<< \Population size = " << setw(5) << p << endl
<< \cMutation set size = " << setw(5) << cMutate << endl
<< \Generation limit = " << setw(5) << gen << \ generations" << endl
<< \Time limit = " << setw(5) << t << \ seconds" << endl << endl;
GAFitnessFile << \Initialising GA population. . . ";
srandom(StartTime = time(NULL)); // Initialise execution time & pseudo random number generator.
for (short int i = 0;i < p;i++) // Initialise GA with random population consisting of (p) playing set candidates.
for (short int j = 0;j < L;j++)
do
for (short int l = 0;l < n;l++)
Population[i][j][l] = ((short int)(((random())/(
oat)RAND MAX)*m)+1); // Generate random ticket.
while (!ValidTicket(Population[i][j],m,n)); // Check whether generated ticket is valid.
GAFitnessFile << \OK! (" << time(NULL)-StartTime << \ s)" << endl << \Initialising GA tness. . . ";
StartTime = time(NULL); // Re-initialise execution time.
fitnessmax = fitnesssum = 0; fitnessmin = 1; TempFitness = FitnessList;
for (short int PopNum = 0;PopNum < p;PopNum++) f NumDominated = 0;
for (short int i = 0;i < n;i++) CurTicket[i] = i+1; // Initialise ticket to [1,2,...,n]
for (long int counter = 1;counter <= NumTickets;counter++) f Intersect = 0; // Check whether current ticket is dominated.
for (short int DomTicketNum = 0;(DomTicketNum < L) && (Intersect < k);DomTicketNum++) f Intersect = dcounter = tcounter = 0;
while ((dcounter < n) && (tcounter < n) && (Intersect < k))
if (Population[PopNum][DomTicketNum][dcounter] < CurTicket[tcounter])
dcounter++;
else if (Population[PopNum][DomTicketNum][dcounter] > CurTicket[tcounter])
tcounter++;
else f // (Population[PopNum][DomTicketNum][dcounter] == CurTicket[tcounter])
Intersect++; dcounter++; tcounter++; // Tickets intersect in 1 element.
g if (Intersect == k) NumDominated++; // Check whether current ticket is dominated by candidate playing set.
gCurTicket[CurrentNumber-1]++; // Generate next ticket in lexicographic sequence.
if (CurTicket[CurrentNumber-1] > m) f CurTicket[CurrentNumber-1]--;
while ((CurrentNumber > 0) && (CurTicket[CurrentNumber-1] == m-(n-CurrentNumber))) CurrentNumber--;
CurTicket[CurrentNumber-1]++;
for (short int i = CurrentNumber;i < n;i++) CurTicket[i] = CurTicket[i-1] + 1;
CurrentNumber = n;
g
gGAPopFit[PopNum] = (
oat)NumDominated/(
oat)NumTickets; // Store playing set candidate fitness.
TempFitness->next = new Fitness; TempFitness = TempFitness->next;
TempFitness->fitness = NumDominated; // Store playing set candidate fitness.
TempFitness->number = PopNum; TempFitness->next = NULL; TempFitness->used = false;
if (GAPopFit[PopNum] > fitnessmax) fitnessmax = GAPopFit[PopNum]; // Store maximum fitness of generation.
if (GAPopFit[PopNum] < fitnessmin) fitnessmin = GAPopFit[PopNum]; // Store minimum fitness of generation.
fitnesssum += NumDominated;
gfitnessavg = fitnesssum/p; // Store average fitness of generation.
cerr << \nished!" << endl;
GAFitnessFile << \OK! (" << time(NULL)-StartTime << \ seconds)" << endl << endl;
cerr << \Genetic algorithm initialised, running. . . (generation limit " << gen << \ generations, time limit " << t << \s)" << endl;
StartTime = time(NULL); // Re-initialise execution time.
GAFitnessFile << \ 0"; // Output initial GA population fitness.
for (TempFitness = FitnessList;TempFitness->next != NULL;TempFitness = TempFitness->next)
GAFitnessFile << setw(9) << setprecision(4) << setiosflags(ios::fixed|ios::showpoint) << TempFitness->next->fitness;
GAFitnessFile << endl;
short int inputgene1, outputgene1, inputgene2, outputgene2, curcandidate, TempArray[L];
long int newcandidate1fitness, newcandidate2fitness;
while ((time(NULL)-StartTime < t) && (curgen++ < gen)) f // Start GA.
GAPopulationFile << \Generation " << setw(4) << curgen << \:" << endl; // Write GA Population to file.
for (short int i = 0;i < L;i++) f for (short int j = 0;j < p;j++) f GAPopulationFile << `f' << Population[j][i][0];
for (short int l = 1;l < n;l++) GAPopulationFile << `,' << Population[j][i][l];
GAPopulationFile << \g ";
gGAPopulationFile << endl;
g
GAPopulationFile << endl;
for (TempFitness = FitnessList,fitnesssum = 0;TempFitness->next != NULL;TempFitness = TempFitness->next) f TempFitness->next->used = TempFitness->next->changed = false; // Candidate has not been used nor changed during
crossover operation/procedure.
fitnesssum += TempFitness->next->fitness; // Determine fitness range.
g // CROSSOVER procedure (mating) relative to fitness of chromosomes (candidate playing sets).
for (short int cocounter = 0;cocounter < p/2;cocounter++) f // Find crossover partners for 1
2 of population.
// Determine crossover partners for crossover procedure.
ccandidate = (((random())/(
oat)RAND MAX)*(
oat)fitnesssum/(
oat)NumTickets); // First mating candidate.
selection = 0; TempFitness = FitnessList;
while (selection < ccandidate) f // Search for chosen first candidate.
while (TempFitness->next->used) TempFitness = TempFitness->next;
selection += (
oat)TempFitness->next->fitness/(
oat)NumTickets; TempFitness = TempFitness->next;
gcandidate1 = TempFitness->number; // Store first crossover candidate.
TempFitness->used = true; // Candidate has been used for crossover during this crossover procedure.
fitnesssum -= TempFitness->fitness; // Remove chosen first candidate from fitness list by rescaling fitness range
for next candidate.
ccandidate = (((random())/(
oat)RAND MAX)*(
oat)fitnesssum/(
oat)NumTickets); // Second mating candidate.
selection = 0; TempFitness2 = FitnessList;
while (selection < ccandidate) f // Search for chosen second candidate.
while (TempFitness2->next->used)
TempFitness2 = TempFitness2->next;
selection += (
oat)TempFitness2->next->fitness/(
oat)NumTickets; TempFitness2 = TempFitness2->next;
gcandidate2 = TempFitness2->number; // Store second crossover candidate.
TempFitness2->used = true; // Candidate has been used for crossover during this crossover procedure.
fitnesssum -= TempFitness2->fitness; // Remove chosen second candidate from fitness list by rescaling fitness range
for next candidate.
// Check which single gene exchange from different crossover candidates would yield fitness increase.
curcandidate = candidate1;
docrossover:
if (curcandidate == candidate2) f // Store evolving maximum fitness.
fitnessmax = (
oat)(TempFitness2->fitness)/(
oat)NumTickets;
candidate2 = candidate1; candidate1 = curcandidate; inputgene2 = -1; // Exchange between crossover candidates.
gelse f // (curcandidate != candidate2) || (curcandidate == candidate1)
fitnessmax = (
oat)(TempFitness->fitness)/(
oat)NumTickets; inputgene1 = -1;
gfor (short int i = 0;i < L;i++) f // First check if input gene is equivalent to any gene in crossover candidate.
Intersect = 0;
for (short int j = 0;(j < L) && (Intersect < k);j++) f dcounter = tcounter = 0; Intersect = k;
while ((dcounter < n) && (tcounter < n) && (Intersect == k))
if (Population[candidate1][j][dcounter] == Population[candidate2][i][tcounter]) f dcounter++; tcounter++;
gelse Intersect = 0; // (Population[candidate1][j][dcounter] != Population[candidate2][i][tcounter])
gif (Intersect < k) f // Input gene is distinct from all genes in first candidate.
for (short int j = 0;j < L;j++) f for (short int l = 0;l < n;l++) f TempArray[l] = Population[candidate1][j][l]; Population[candidate1][j][l] = Population[candidate2][i][l];
gNumDominated = 0; // Recalculate chromosome fitness with new gene.
for (short int l = 0;l < n;l++) CurTicket[l] = l+1; // Initialise ticket to [1,2,...,n]
for (long int counter = 1;counter <= NumTickets;counter++) f Intersect = 0; // Check whether current ticket is dominated.
for (short int DomTicketNum = 0;(DomTicketNum < L) && (Intersect < k);DomTicketNum++) f Intersect = dcounter = tcounter = 0;
while ((dcounter < n) && (tcounter < n) && (Intersect < k))
if (Population[candidate1][DomTicketNum][dcounter] < CurTicket[tcounter]) dcounter++;
else if (Population[candidate1][DomTicketNum][dcounter] > CurTicket[tcounter]) tcounter++;
else f // (Population[candidate1][DomTicketNum][dcounter] == CurTicket[tcounter])
Intersect++; dcounter++; tcounter++; // Tickets intersect in 1 element.
g if (Intersect == k) // Check whether current ticket is dominated by candidate playing set.
NumDominated++;
gCurTicket[CurrentNumber-1]++; // Generate next ticket in lexicographic sequence.
if (CurTicket[CurrentNumber-1] > m) f CurTicket[CurrentNumber-1]--;
while ((CurrentNumber > 0) && (CurTicket[CurrentNumber-1] == m-(n-CurrentNumber))) CurrentNumber--;
CurTicket[CurrentNumber-1]++;
for (short int l = CurrentNumber;l < n;l++) CurTicket[l] = CurTicket[l-1] + 1;
CurrentNumber = n;
g
gif (((
oat)NumDominated/(
oat)NumTickets) > fitnessmax) f // Store specific gene exchange information.
fitnessmax = (
oat)NumDominated/(
oat)NumTickets;
if (curcandidate == TempFitness->number) f inputgene1 = j; outputgene1 = i; newcandidate1fitness = NumDominated;
g
A.7. Intelligent genetic algorithm (Algorithm 7) 171
else f // (curcandidate != TempFitness->number) || (curcandidate == TempFitness2->number)
inputgene2 = j; outputgene2 = i; newcandidate2fitness = NumDominated;
g
g // Copy gene information back to candidate.
for (short int l = 0;l < n;l++) Population[candidate1][j][l] = TempArray[l];
g
g
gif (curcandidate != TempFitness2->number) f // Repeat crossover procedure for other crossover candidate.
curcandidate = candidate2; goto docrossover;
g // If an exchange in genes is considered reasonable (causes fitness increase).
if (inputgene1 > -1) f // Change first crossover candidate.
TempFitness->fitness = newcandidate1fitness; // Change candidate 1 fitness.
TempFitness->changed = true; // Candidate was changed during crossover operation/procedure.
for (short int j = 0;j < n;j++) f TempArray[j] = Population[candidate2][inputgene1][j];
Population[TempFitness->number][inputgene1][j] = Population[TempFitness2->number][outputgene1][j];
g
gif (inputgene2 > -1) f // Change second crossover candidate.
TempFitness2->fitness = newcandidate2fitness; // Change candidate 2 fitness.
TempFitness2->changed = true; // Candidate was changed during crossover operation/procedure.
if (inputgene1 == outputgene2)
for (short int j = 0;j < n;j++) Population[TempFitness->number][inputgene2][j] = TempArray[j];
else // (inputgene1 != outputgene2)
for (short int j = 0;j < n;j++)
Population[TempFitness2->number][inputgene2][j] = Population[TempFitness->number][outputgene2][j];
g
gfor (short int i = 0;i < cMutate;i++) f // MUTATE (gMutate) elements of cMutate candidates of the population (p).
candidate1 = (short int)((random()/(
oat)RAND MAX)*p); TempFitness = FitnessList;
while (TempFitness->next->number < candidate1) // Search for selected mutation candidate.
TempFitness = TempFitness->next;
for (short int j = 0;j < gMutate;j++) f candidate2 = (short int)((random()/(
oat)RAND MAX)*L);
do // Move current domination ticket to nearest neighbour (maybe further).
Population[candidate1][candidate2][(short int)((random()/(
oat)RAND MAX)*n)] =
((short int)(((random())/(
oat)RAND MAX)*m)+1);
while (!ValidTicket(Population[candidate1][candidate2],m,n)); // Check whether generated ticket is valid.
gNumDominated = 0; // Recalculate mutated chromosome fitness.
for (short int j = 0;j < n;j++) CurTicket[j] = j+1; // Initialise ticket to [1,2,...,n].
for (long int counter = 0;counter < NumTickets;counter++) f Intersect = 0;
// Check whether current ticket is dominated.
for (short int DomTicketNum = 0;(DomTicketNum < L) && (Intersect < k);DomTicketNum++) f Intersect = dcounter = tcounter = 0;
while ((dcounter < n) && (tcounter < n) && (Intersect < k))
if (Population[candidate1][DomTicketNum][dcounter] < CurTicket[tcounter]) dcounter++;
else if (Population[candidate1][DomTicketNum][dcounter] > CurTicket[tcounter]) tcounter++;
else f // (Population[candidate1][DomTicketNum][dcounter] == CurTicket[tcounter])
Intersect++; dcounter++; tcounter++; // Tickets intersect in 1 element.
g if (Intersect == k) NumDominated++; // Check whether current ticket is dominated by candidate playing set.
gCurTicket[CurrentNumber-1]++; // Generate next ticket in lexicographic sequence.
if (CurTicket[CurrentNumber-1] > m) f CurTicket[CurrentNumber-1]--;
while ((CurrentNumber > 0) && (CurTicket[CurrentNumber-1] == m-(n-CurrentNumber))) CurrentNumber--;
CurTicket[CurrentNumber-1]++;
for (short int j = CurrentNumber;j < n;j++) CurTicket[j] = CurTicket[j-1] + 1;
CurrentNumber = n;
g
gTempFitness->next->fitness = NumDominated; // New fitness of mutated candidate.
gGAFitnessFile << setw(3) << curgen; // Write population fitness to file.
for (TempFitness = FitnessList;TempFitness->next != NULL;TempFitness = TempFitness->next)
GAFitnessFile << setw(9) << TempFitness->next->fitness;
GAFitnessFile << endl; cerr << `.';
if ((long int)(curgen/20) == (
oat)curgen/20) cerr << \ (" << setw(4) << curgen << \/" << gen << \)" << endl;
gGAFitnessFile << \GA simulation time: " << time(NULL)-StartTime << \s." << endl;
GAFitnessFile.close(); // Close the Genetic Algorithm (GA) Fitness file.
GAPopulationFile.close(); // Close the Genetic Algorithm (GA) Population file.
cout << endl;
return 0; // Exit program.
g