哈夫曼编码优于二进制编码案例：

假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。
解：

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，

按哈夫曼规则建立哈夫曼树如图：



方案一（哈夫曼编码）：



方案二（二进制编码）：



方案一带权路径长度计算如下：

WPL=2*（0.19+0.32+0.21）+4*（0.07+0.06+0.10）+5*（0.02+0.03）=2.61

方案二带权路径长度计算如下：

WPL=3*（0.07+0.19+0.02+0.06+0.32+0.03+0.21+0.10）=3

结论：本案例哈夫曼编码优于等长二进制编码。

目标函数
编码方式
本程序采用的是二进制编码精确到小数点后五位，经过计算可知对于
 其编码长度为18，对于 
 其编码长度为15，因此每个基于的长度为33。
参数设置
算法步骤
设计的程序主要分为以下步骤：1、参数设置；2、种群初始化；3、用轮盘赌方法选择其中一半较好的个体作为父代；4、交叉和变异；5、更新最优解；6、对最有个体进行自学习操作；7结果输出。其算法流程图为：
算法结果
由程序输出可知其最终优化结果为38.85029，
输出基因编码为[1 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1]。
代码
import numpy as np
import random
import math
import copy
class Ind():
def __init__(self):
self.fitness = 0
self.x = np.zeros(33)
self.place = 0
self.x1 = 0
self.x2 = 0
def Cal_fit(x, upper, lower): #计算适应度值函数
Temp1 = 0
for i in range(18):
Temp1 += x[i] * math.pow(2, i)
Temp2 = 0
for i in range(18, 33, 1):
Temp2 += math.pow(2, i - 18) * x[i]
x1 = lower[0] + Temp1 * (upper[0] - lower[0])/(math.pow(2, 18) - 1)
x2 = lower[1] + Temp2 * (upper[1] - lower[1])/(math.pow(2, 15) - 1)
if x1 > upper[0]:
x1 = random.uniform(lower[0], upper[0])
if x2 > upper[1]:
x2 = random.uniform(lower[1], upper[1])
return 21.5 + x1 * math.sin(4 * math.pi * (x1)) + x2 * math.sin(20 * math.pi * x2)
def Init(G, upper, lower, Pop): #初始化函数
for i in range(Pop):
for j in range(33):
G[i].x[j] = random.randint(0, 1)
G[i].fitness = Cal_fit(G[i].x, upper, lower)
G[i].place = i
def Find_Best(G, Pop):
Temp = copy.deepcopy(G[0])
for i in range(1, Pop, 1):
if G[i].fitness > Temp.fitness:
Temp = copy.deepcopy(G[i])
return Temp
def Selection(G, Gparent, Pop, Ppool): #选择函数
fit_sum = np.zeros(Pop)
fit_sum[0] = G[0].fitness
for i in range(1, Pop, 1):
fit_sum[i] = G[i].fitness + fit_sum[i - 1]
fit_sum = fit_sum/fit_sum.max()
for i in range(Ppool):
rate = random.random()
Gparent[i] = copy.deepcopy(G[np.where(fit_sum > rate)[0][0]])
def Cross_and_Mutation(Gparent, Gchild, Pc, Pm, upper, lower, Pop, Ppool): #交叉和变异
for i in range(Ppool):
place = random.sample([_ for _ in range(Ppool)], 2)
parent1 = copy.deepcopy(Gparent[place[0]])
parent2 = copy.deepcopy(Gparent[place[1]])
parent3 = copy.deepcopy(parent2)
if random.random() < Pc:
num = random.sample([_ for _ in range(1, 32, 1)], 2)
num.sort()
if random.random() < 0.5:
for j in range(num[0], num[1], 1):
parent2.x[j] = parent1.x[j]
else:
for j in range(0, num[0], 1):
parent2.x[j] = parent1.x[j]
for j in range(num[1], 33, 1):
parent2.x[j] = parent1.x[j]
num = random.sample([_ for _ in range(1, 32, 1)], 2)
num.sort()
num.sort()
if random.random() < 0.5:
for j in range(num[0], num[1], 1):
parent1.x[j] = parent3.x[j]
else:
for j in range(0, num[0], 1):
parent1.x[j] = parent3.x[j]
for j in range(num[1], 33, 1):
parent1.x[j] = parent3.x[j]
for j in range(33):
if random.random() < Pm:
parent1.x[j] = (parent1.x[j] + 1) % 2
if random.random() < Pm:
parent2.x[j] = (parent2.x[j] + 1) % 2
parent1.fitness = Cal_fit(parent1.x, upper, lower)
parent2.fitness = Cal_fit(parent2.x, upper, lower)
Gchild[2 * i] = copy.deepcopy(parent1)
Gchild[2 * i + 1] = copy.deepcopy(parent2)
def Choose_next(G, Gchild, Gsum, Pop): #选择下一代函数
for i in range(Pop):
Gsum[i] = copy.deepcopy(G[i])
Gsum[2 * i + 1] = copy.deepcopy(Gchild[i])
Gsum = sorted(Gsum, key = lambda x: x.fitness, reverse = True)
for i in range(Pop):
G[i] = copy.deepcopy(Gsum[i])
G[i].place = i
def Decode(x):   #解码函数
Temp1 = 0
for i in range(18):
Temp1 += x[i] * math.pow(2, i)
Temp2 = 0
for i in range(18, 33, 1):
Temp2 += math.pow(2, i - 18) * x[i]
x1 = lower[0] + Temp1 * (upper[0] - lower[0]) / (math.pow(2, 18) - 1)
x2 = lower[1] + Temp2 * (upper[1] - lower[1]) / (math.pow(2, 15) - 1)
if x1 > upper[0]:
x1 = random.uniform(lower[0], upper[0])
if x2 > upper[1]:
x2 = random.uniform(lower[1], upper[1])
return x1, x2
def Self_Learn(Best, upper, lower, sPm, sLearn): #自学习操作
num = 0
Temp = copy.deepcopy(Best)
while True:
num += 1
for j in range(33):
if random.random() < sPm:
Temp.x[j] = (Temp.x[j] + 1)%2
Temp.fitness = Cal_fit(Temp.x, upper, lower)
if Temp.fitness > Best.fitness:
Best = copy.deepcopy(Temp)
num = 0
if num > sLearn:
break
return Best
if __name__ == '__main__':
upper = [12.1, 5.8]
lower = [-3, 4.1]
Pop = 100
Ppool = 50
G_max = 300
Pc = 0.8
Pm = 0.1
sPm = 0.05
sLearn = 20
G = np.array([Ind() for _ in range(Pop)])
Gparent = np.array([Ind() for _ in range(Ppool)])
Gchild = np.array([Ind() for _ in range(Pop)])
Gsum = np.array([Ind() for _ in range(Pop * 2)])
Init(G, upper, lower, Pop)  #初始化
Best = Find_Best(G, Pop)
for k in range(G_max):
Selection(G, Gparent, Pop, Ppool)  #使用轮盘赌方法选择其中50%为父代
Cross_and_Mutation(Gparent, Gchild, Pc, Pm, upper, lower, Pop, Ppool) #交叉和变异生成子代
Choose_next(G, Gchild, Gsum, Pop)  #选择出父代和子代中较优秀的个体
Cbest = Find_Best(G, Pop)
if Best.fitness < Cbest.fitness:
Best = copy.deepcopy(Cbest)  #跟新最优解
else:
G[Cbest.place] = copy.deepcopy(Best)
Best = Self_Learn(Best, upper, lower, sPm, sLearn)
print(Best.fitness)
x1, x2 = Decode(Best.x)
print(Best.x)
print([x1, x2])
以上这篇Python实现遗传算法(二进制编码)求函数最优值方式就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持脚本之家。

大家对哈弗曼编码应该很熟悉，哈弗曼编码最大的一个用处就是压缩存储，本文要讲的不是如何编码，而是求出对字符串编码后的二进制位的长度。
估计一般的同学都会有思路，最简单的思路就是先构建好哈弗曼树，然后编码，然后求长度，这个思路很简单但是下面给出一个用c++写的一个程序，
效率比较高：


    #include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>

#include <iostream>
using namespace std;
/*本程序 统计 用哈弗曼编码 编一个字符串   最后编码的二进制位数*/
int main()
{
    char s[3300];
    while(scanf("%s",s) != EOF)
    {
        int n = strlen(s);
        sort(s,s + n);
        priority_queue<int> heap;
        int cnt = 0;
        for(int i = 0,j; i < n;)
        {
            j = i;
            while(j < n && s[j] == s[i]) ++ j;
            heap.push(i - j);
            i = j;
            ++ cnt;
        }
        int ret = 0;
        for(int i = 0; i < cnt - 1; ++ i)
        {
            int A = heap.top();
            heap.pop();
            int B = heap.top();
            heap.pop();
            ret -= A + B;
            heap.push(A + B);
        }
        printf("%d\n",ret);
    }
    return 0;
}


还望与大家一起感受编程的精妙。

转自： 
http://www.cnblogs.com/algorithms/archive/2012/05/19/2509322.html



 /*
  用遗传算法求y=x*sin(10*pi*x)+2的最大值  -1=<x<=2
  精确到6位小数
  pow(2,21)<3*1000000<pow(2,22)
  编码的二进制长度为22 
  */
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <ctime>
 #include <math.h>

 #define N 3000000
 #define PI 3.14159265
 #define MAX(a,b) ((a)>(b)?(a):(b))

 #define SIZE  50
 #define MAXGEN  50
 #define P_CORSS 0.75
 #define P_MUTATION 0.05

 #define LEN 22

 typedef struct node
 {
      char x[LEN];
      double fitness,fitsum;
 }node;

 node cur[SIZE],next[SIZE],max,min;

  double randd()
  {
    return (double)rand()/RAND_MAX;
  }
  int randi(int k)
  {
    return (int)(randd()*k+0.5);
  }

  //计算当前种群中各个个体的适应度 
  void cal_fitness()
  {
    int i,j,k;
    double d;
    for(i=0;i<SIZE;i++)
    {
      k=0;
      for(j=LEN-1;j>=0;j--) 
          k=(k<<1)+cur[i].x[j];
      d=(double)k/N*3-1;
      cur[i].fitness=d*sin(10*PI*d)+2;
      cur[i].fitsum=i>0?(cur[i].fitness+cur[i-1].fitsum):(cur[0].fitness);
    }
  }

  void init()
  {
    int tmp;
    for(int i=0;i<SIZE;i++)
    {
      tmp=randi(N);
      for(int j=0;j<LEN;j++)
      {
       cur[i].x[j]=tmp%2;
        tmp=tmp>>1;
      }
    }
    cal_fitness();
  }

  int sel()  //选择
  {
    double p=randd();
    double sum=cur[SIZE-1].fitsum;
    for(int i=0;i<SIZE;i++)
    {
      if(cur[i].fitsum/sum>p) return i;
    }
  }

  //换代 
  void tran()
  {
    int i,j,pos;
    //找当前种群最优个体 
    max=cur[0];
    for(i=1;i<SIZE-1;i++)
    {
      if(cur[i].fitness>max.fitness)  max=cur[i];
    }
    for(int k=0;k<SIZE;k+=2)
    {
      //选择交叉个体 
      i=sel();
      j=sel();

      //选择交叉位置 
      pos=randi(LEN-1);

     //交叉
     if(randd()<P_CORSS)
     {
       memcpy(next[k].x,cur[i].x,pos);
       memcpy(next[k].x+pos,cur[j].x+pos,LEN-pos);

       memcpy(next[k+1].x,cur[j].x,pos);
       memcpy(next[k+1].x+pos,cur[i].x+pos,LEN-pos);
     }
     else
     {
       memcpy(next[k].x,cur[i].x,LEN);
       memcpy(next[k+1].x,cur[j].x,LEN);
     }
     //变异
     if(randd()<P_MUTATION)
     {
       pos=randi(LEN-1);
       next[k].x[pos]^=next[k].x[pos];

       pos=randi(LEN-1);
       next[k+1].x[pos]^=next[k+1].x[pos];
     }
   }
   //找下一代的最差个体 
   min=next[0],j=0;
   for(i=1;i<SIZE-1;i++)
   {
     if(next[i].fitness<min.fitness)  min=next[i],j=i;
   }
   //用上一代的最优个体替换下一代的最差个体
   next[j]=max;

   memcpy(cur,next,sizeof(cur));

   cal_fitness();
 }

 //打印个体适应度和二进制编码 
 void print(node tmp)
 {
   printf("%.6lf",tmp.fitness);
   for(int i=0;i<LEN;i++)  printf(" %d",tmp.x[i]);
   printf("\n");
 }

 //打印种群
 void printcur()
 {
   for(int i=0;i<SIZE;i++) 
       print(cur[i]);
 } 

 void GA()
 {
   int cnt=0;
   double ans;
   while(cnt++<MAXGEN)
   {
     tran();
   }
   ans=cur[0].fitness;
   for(int i=1;i<SIZE;i++) 
       ans=MAX(ans,cur[i].fitness);
   printf("%.6lf\n",ans);
 }

 int main()
 {
   srand((unsigned)time(NULL));

   init();
   GA();

   system("pause");
   return 0;
 }