一种启发式频率分配算法

减小字体

增大字体作者：佚名来源：本站整理发布时间：2009-01-10 12:07:18

程的选择机制，采用计算适应值的方法来评估一个候选解的优劣。
遗传算法求解问题的基本步骤可以描述如下：
1. 首先生成一组初始的候选解群体(假设为N个候选解个体)，称为第0代；
2. 计算群体中各个候选解的适应值；
3. 如果有候选解满足算法终止条件，算法终止，否则继续4；
4. 根据交配概率，将候选解群体中的个体随机两两配对，进行交配操作以生成新的候选解；
5. 根据变异概率，对4中生成的候选解群中的每个个体进行变异操作；
6. 使用选择机制形成新一代候选解；转2。
GA算法具有下述特点： GA是对问题参数的编码组进行，而不是直接对参数本身；GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始；GA使用目标函数值（适应度）这一信息进行搜索，而不需导数等其他信息；GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。
遗传算法通过编码和遗传操作，达到了处理的并行性，可以同时处理群体中的多个个体，即同时对搜索空间内的多个解进行评估，具有较好的全局搜索性能，减少了限于局部最优解的风险。
3. 遗传算法用于频率分配
3．1 算法的基本流程
采用遗传算法的FAP基本流程
3．2 遗传算子的选择
3．2．1 选择算子
选择算子在父代群体中选出父体和母体。生物界中，父母亲素质比较高的其后代素质高的概率也大。模拟这种现象，在FAP中选择算子采用轮赌算法实现。
轮赌算法流程如下：
　　sum=0; i=0;
　　wheelpos=rand()*sumfitness;
　　for(sum<wheelpos && i<pop-size)
　　｛
　　　i++;
　　　if(i≥pop-size)
　　　　｛
　　　　sum=0; i=0
　　　　wheelpos=rand()*sumfitness;
　　　　｝
　　　j=rand()*pop-size;
　　　sum+=fitness［j］;
　　｝
　　return j;

3．2．2 交叉算子
交叉算子让父体和母体互相交换某部分基因而产生下一代个体的雏形，起全局搜索的作用。交叉算子通常有单点交叉、双点交叉、多点交叉等等。在频率自动分配的算法中，为了不破坏基因段内部频点间的关系，采用单点交叉和双点交叉比较合适。此外，在生物界中并不是两个个体相遇了就一定会结合，模拟此现象，引入交叉因子pc。
其基本流程如下：
　　//flip函数中，产生一个0到1的随机数，若小于pc，则返回1，否则返回0
if(flip(pc))
　　　crossover1(mother,father);
　　else if(flip(pc))
　　　　　crossover2(mother,father);
　　else
　　　　　copy(mother);
　　　　　copy(father);

3．2．3 变异算子
变异算子对后代个体的某些基因进行变异，起局部搜索的作用.生物界中，父母的染色体交叉后产生后代个体的染色体雏形，这个雏形在成长过程中会发生基因的变异，正是这种变异使得下一代的群体中会出现各种特征的个体.另外，生物界中并非每个基因都会变异，模拟此现象，引入变异因子pm，使用方法与交叉因子类似。
其基本流程如下：
　　while(all frequentpoint)
　　　{
if(flip(pm))　mutate(frequentpoint)；}
4. 工程上需要注意的问题
4．1 初始候选种群
由于遗传算法和其它启发式算法一样，不对全部解空间进行穷举搜索，因此初始的候选解群体的选择会对得到最终解的速度和质量有影响。初始的候选解群体在解空间内分布得越均匀，它们拥有的遗传基因就越有代表性。实践中采用文献[7]的GECP得到以各个顶点为主顶点的可行解作为初始候选种群。
4．2 编码方案
编码就是用一种数字排列方案来表示问题的解的方法，利用编码将问题的解空间映射到GA算法的编码空间。编码方案的选择依赖于问题的性质，并影响到算法内操作的设计，是影响算法性能的重要因素。常见的编码方案有二进制编码、十进制编码、实数编码等。频率分配问题适合采用十进制编码方案，每个码表示一条通信链路，码值表示分配的信道编号。
4．3 适配值函数
适配值函数对个体（频率分配方案）进行评价，也是优化过程发展的依据。可以采用如下方式来计算适应度：　
fitness=1000 / Σ (pri×seperate(Freq))。
其中：
pri 是节点的加权值；
函数seperate(Freq)是节点中各条链路发频率同其它链路的收频率间隔的和；