🚀 go-pugleaf

���λ�ã������� -- ��ݽṹ���㷨 -- �Ŵ��㷨
�Ŵ��㷨
���ߣ�HITMAN �༭
�Ŵ��㷨(Genetic Algorithm, GA)�ǽ��귢չ������һ��ո�µ�ȫ���Ż��㷨�����
���������Ŵ�ѧ�Ĺ۵㣬ͨ����Ȼѡ���Ŵ�����������û��ƣ�ʵ�ָ����������Ӧ
�Ե���ߡ���һ����������Ȼ����"�ﾺ�����������"�Ľ��̡�
1962��Holland�����״������GA�㷨��˼�룬�Ӷ������˴�����о��ߣ�Ѹ���ƹ㵽��
��������������ѧϰ�ȷ��棬���춨�˼�ʵ�����ۻ�
���Ŵ��㷨�������ʱ������Ҫ�Դ��������ģ�ͽṹ�Ͳ�����б��룬һ�����ַ�
����ʾ�������̾ͽ������Ż�����ɢ���ˡ�Ҳ��������ռ䶨���GA(Genetic Alg
orithm in Continuous Space, GACS)���ݲ����ۡ�
һ������������Ŵ��㷨(Seguential Genetic Algoritm, SGA)�����¹�̽��У�
(1) �Դ���������б��룻
(2) ����ʼ��Ⱥ��X(0):=(x1, x2, �� xn)��
(3) �Ե�ǰȺ��X(t)��ÿ������xi��������Ӧ��F(xi)����Ӧ�ȱ�ʾ�˸ø�������ܺû�
��
(4) Ӧ��ѡ�����Ӳ����м��Xr(t)��
(5) ��Xr(t)Ӧ����������ӣ�������һ��Ⱥ��X(t+1)����Щ���ӵ�Ŀ��������չ���޸�
��ĸ����棬����ȫ��������˼�룻
(6) t:=t+1�����������ֹ��������(3)��
GA����õ����������¼��֣�
(1) ѡ������(selection/reproduction): ѡ�����Ӵ�Ⱥ���а�ijһ���ʳɶ�ѡ�����
��ij����xi��ѡ��ĸ���Pi������Ӧ��ֵ����ȡ���ͨ����ʵ�ַ��������̶�(roulett
e wheel)ģ�͡�
(2) ��������(Crossover): �������ӽ���ѡ�е���������Ļ�����������pc���н��棬
��������µĸ��壬����λ�������ġ�����Pc��һ��ϵͳ����
(3) ��������(Mutation): �������ӽ��¸���Ļ������ĸ�λ������pm���б��죬�Զ�
ֵ������(0,1����)��˵����ȡ����
�����������ӵ�ʵ���Ƕ��ֶ���ģ���������µ��������ڲ��ϵ�������ԸĽ�GA��ij
Щ���ܡ�ϵͳ����(������n,����������l,�������Pc,�������Pm��)���㷨�������ٶ�
������кܴ��Ӱ�죬Ӧ�Ӿ�������ѡȡ��ͬ��ֵ��
GA�ij������Ӧ���ǵ�ͨ���ԣ�����Ҫ�н�ǿ����Ӧ�µ����ӵ�������OOP�е���ļ̳�
Ϊ�����ṩ����һ���ܡ�����������ṹ������(ALLELE)�͸���(INDIVIDUAL)���Ը�
��ļ�����ΪȺ����TPopulation����ݳ�Ա����TSGA������Ⱥ���������������GA�Ļ�
������������һ��Ӧ��ʵ�������TSGA�������������µIJ�����
TPopulation���������Ҫ��̣�
FillFitness: ���ۺ����ÿ��������н���(decode)�����������Ӧ��ֵ���������
���û�����ʵ�֡�
Statistic: �Ե�ǰȺ�����ͳ�ƣ���������Ӧ��sumfitness��ƽ����Ӧ��average����
�ø���fmax�������fmin�ȡ�
SGA�Ľṹ���ඨ������(��C++��д)��
typedef char ALLELE; // ��������
typedef struct{
ALLELE *chrom;
float fitness; // fitness of Chromosome
}INDIVIDUAL; // ���嶨��
class TPopulation{ // Ⱥ���ඨ��
public:
int size; // Size of population: n
int lchrom; // Length of chromosome: l
float sumfitness, average;
INDIVIDUAL *fmin, *fmax;
INDIVIDUAL *pop;
TPopulation(int popsize, int strlength);
~TPopulation();
inline INDIVIDUAL &Individual(int i){ return pop[i];};
void FillFitness(); // ���ۺ���
virtual void Statistics(); // ͳ�ƺ���
};
class TSGA : public TPopulation{ // TSGA��������Ⱥ����
public:
float pcross; // Probability of Crossover
float pmutation; // Probability of Mutation
int gen; // Counter of generation
TSGA(int size, int strlength, float pm=0.03, float pc=0.6):
TPopulation(size, strlength)
{gen=0; pcross=pc; pmutation=pm; } ;
virtual INDIVIDUAL& Select();
virtual void Crossover(INDIVIDUAL &parent1, INDIVIDUAL
&parent2,INDIVIDUAL &child1, INDIVIDUAL &child2);
virtual ALLELE Mutation(ALLELE alleleval);
virtual void Generate(); // �����µ�һ��
};
�û�GA�ඨ�����£�
class TSGAfit : public TSGA{
public:
TSGAfit(int size,float pm=0.0333,float pc=0.6)
:TSGA(size,24,pm,pc){};
void print();
};
����GA��һ�����ʹ�̣�����ÿ�ε�������Dz�һ��ģ�ϵͳ����ͬ��������Ҳ
��ͬ����ʵ���в���һ��ѡȡ���£�������n=50-200���������Pm=0.03, �������Pc=
0.6���������̫�󣬻ᵼ�²��ȶ���
�ύʱ�䣺2003-12-12
������Դ����
�Ķ�����132


--

��������
�� ��Դ:�����Ļ����� bbs.cqupt.edu.cn��[FROM: dangdang]