Catégorie intelligence artificielle, exemple d'un algorithme génétique. Liens utiles à la compréhension dans la source
Conclusion :
Dès fois le programme ne trouvera pas la cible avant la limite de 125 tentatives mais c'est assez rare.
Merci aux sites qui m'ont aidé.
4 mai 2015 à 12:54
Modifié par 3roub le 2/01/2015 à 17:26
13 avril 2012 à 18:34
4 juin 2005 à 14:55
#include
#include <windows.h>
#include <math.h>
#include <string>
#include <vector>
#include
#include <time.h>
// TAILLE DE LA POPULATION
#define PRGM_TAILLEPOPULATION 8192 // logiquement, plus il y a de membres, plus il y a de chances d'en trouver un de bon
// MAXIMUM DE POSSIBILITES (OU D'ESSAIS)
// -> il se peut qu'aucune solution ne soit trouvée alors pas la peine d'attendre
#define PRGM_MAXESSAIS 1250
// TAUX DE MUTATION
#define PRGM_TAUXMUTATION 4 // plus c'est grand, plus il y aura de chance d'avoir de "bons" membres dans chaque génération
#define PRGM_MUTATION RAND_MAX * PRGM_TAUXMUTATION
// TAUX D'ELITISME
#define PRGM_TAUXELITISME 0.10 // voir définition de "élitisme" -> le fait de ne s'occuper QUE des meilleurs : plus le chiffre
// est bas, et moins il y aura de "meilleurs" affichés (0.10 = un seul)
// LA CIBLE : la chaîne de caractère "Vive l'IA !" parmis la population (le nom d'un membre par exemple)
using namespace std;
struct prgm_structure
{
string nom;
unsigned int fitness;
// -> A chaque génération, les individus dont le fitness est le plus élevé seront sélectionnés afin de transmettre
// leur caractère génétique à leurs descendants (plus le fitness est élévé, plus les gènes correspondants sont pertinents)
};
typedef vector prgm_vecteur;
string prgm_cible;
// INITIALISATION DE LA POPULATION
void initialisation_population(prgm_vecteur &population, prgm_vecteur &buffer)
{
int taillecible = prgm_cible.size();
for (int i = 0; i < PRGM_TAILLEPOPULATION; i++)
{
prgm_structure individu;
individu.fitness = 0;
individu.nom.erase();
for (int j = 0; j < taillecible; j++)
{
individu.nom += (rand() % 90) + 32;
}
population.push_back(individu);
}
buffer.resize(PRGM_TAILLEPOPULATION);
}
// FITNESS
void calcul_fitness(prgm_vecteur &population)
{
string cible = prgm_cible;
int taillecible = cible.size();
unsigned int fitness;
for (int i = 0; i < PRGM_TAILLEPOPULATION; i++)
{
fitness = 0;
for (int j = 0; j < taillecible; j++)
{
fitness += abs(int(population[i].nom[j] - cible[j]));
}
population[i].fitness = fitness;
}
}
// TRI
bool trier_fitness(prgm_structure x, prgm_structure y)
{
return (x.fitness < y.fitness);
}
void trier_par_fitness(prgm_vecteur &population)
{
sort(population.begin(), population.end(), trier_fitness);
}
// ELITISME
void elitisme( prgm_vecteur &population, prgm_vecteur &buffer, int tailleelitisme )
{
for (int i = 0; i < tailleelitisme; i++)
{
buffer[i].nom = population[i].nom;
buffer[i].fitness = population[i].fitness;
}
}
// MUTATION
void mutation(prgm_structure &membre)
{
int taillecible = prgm_cible.size();
int c = rand() % taillecible;
int d = (rand() % 90) + 32;
membre.nom[c] = ((membre.nom[c] + d) % 122);
}
// JOINDRE
void joindre(prgm_vecteur &population, prgm_vecteur &buffer)
{
int tailleelitisme = PRGM_TAILLEPOPULATION * PRGM_TAUXELITISME;
int taillecible = prgm_cible.size(), e, iun, ideux;
elitisme(population, buffer, tailleelitisme);
for (int i = tailleelitisme; i < PRGM_TAILLEPOPULATION; i++)
{
iun = rand() % (PRGM_TAILLEPOPULATION / 2);
ideux = rand() % (PRGM_TAILLEPOPULATION / 2);
e = rand() % taillecible;
buffer[i].nom = population[iun].nom.substr(0, e) + population[ideux].nom.substr(e, tailleelitisme - e);
if (rand() < PRGM_MUTATION) mutation(buffer[i]);
}
}
// AFFICHAGE DU MEILLEUR INDIVIDU : SON NOM ET SON FITNESS
void affiche_meilleur(prgm_vecteur &vecalgogenetique)
{
CONSOLE_SCREEN_BUFFER_INFO csbiInfo;
HANDLE HCmd = GetStdHandle(STD_OUTPUT_HANDLE);
GetConsoleScreenBufferInfo(HCmd, &csbiInfo);
SetConsoleTextAttribute(HCmd, FOREGROUND_BLUE|FOREGROUND_INTENSITY);
cout << "Le meilleur : " << flush;
SetConsoleTextAttribute(HCmd, FOREGROUND_GREEN);
cout << vecalgogenetique[0].nom << flush;
SetConsoleTextAttribute(HCmd, FOREGROUND_RED|FOREGROUND_INTENSITY);
cout << " [" << vecalgogenetique[0].fitness << "]" << endl;
}
// CROSSOVER
// -> Echanger les gènes des individus deux à deux pour créer les enfants
// exemple :
// individu 5 : 1-1-0|-0-1-1-1-0
// individu 1 : 0-1-1|-1-0-0-1-1
//
// va donner :
//
// enfant 1 : 1-1-0|-1-0-0-1-1
// enfant 2 : 0-1-1|-0-1-1-1-0
void echange(prgm_vecteur *&population, prgm_vecteur *&buffer)
{
prgm_vecteur *temp population; population buffer; buffer = temp;
}
int main()
{
srand(unsigned(time(NULL)));
char strTmp[256];
scanf("%s",&strTmp);
prgm_cible = strTmp;
prgm_vecteur population_a, population_b;
prgm_vecteur *population, *buffer;
initialisation_population(population_a, population_b);
population = &population_a;
buffer = &population_b;
for (int i = 0; i < PRGM_MAXESSAIS; i++)// de 0 à 125 :
{
calcul_fitness(*population);
trier_par_fitness(*population);
affiche_meilleur(*population);
if ((*population)[0].fitness == 0) break;// si le fitness d'un membre = 0, c'est qu'il n'y a pas de meilleur individu et
// donc, que c'est la cible
joindre(*population, *buffer);// joindre la population ensemble
echange(population, buffer);
}
// PAS DE SOLUTION
if ( i >= PRGM_MAXESSAIS)
{
HANDLE HCmd = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(HCmd, FOREGROUND_RED|FOREGROUND_INTENSITY);
cout << "Aucune solution trouv\202e, maximum d'essais d\202pass\202 ..." << endl;
SetConsoleTextAttribute(HCmd, FOREGROUND_GREEN);
system("pause");
return 0;
}
// SOLUTION TROUVEE !
HANDLE HCmd = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(HCmd, FOREGROUND_GREEN|FOREGROUND_INTENSITY);
cout << "Cible trouv\202e !" << endl;
SetConsoleTextAttribute(HCmd, FOREGROUND_GREEN);
system("pause");
return 0;
}
Sauf que ça ne prend que le premier mot (ça s'arrête au premier signe espace ' ').... Je sais pas trop comment fonctionne la classe string
3 juin 2005 à 10:17
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.