當前位置:首頁 » 操作系統 » 遺傳演算法背包問題

遺傳演算法背包問題

發布時間: 2022-09-23 20:07:38

1. 如何通俗易懂地解釋遺傳演算法

遺傳演算法,核心是達爾文優勝劣汰適者生存的進化理論的思想。

我們都知道一個種群,通過長時間的繁衍,種群的基因會向著更適應環境的趨勢進化,牛B個體的基因被保留,後代越來越多,適應能力低個體的基因被淘汰,後代越來越少。經過幾代的繁衍進化,留下來的少數個體,就是相對能力最強的個體了。

那麼在解決一些問題的時候,我們能不能學習這樣的思想,比如先隨機創造很多很多的解,然後找一個靠譜的評價體系,去篩選比較好的解,再用這些好的解像生小寶寶一樣生一堆可能更好的解,然後再篩再生,反復弄個幾代,得到的說不定就是近似最優解喲

說干就干,有一個經典組合問題叫「背包問題」,我們拿這種思路來試試

「背包問題(Knapsack Problem)是一種組合優化的NP完全問題。問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內,我們如何選擇,才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。」

這個問題的衍生簡化問題「0-1背包問題」 增加了限制條件:每件物品只有一件,可以選擇放或者不放,更適合我們來舉例

這樣的問題如果數量少,當然最好選擇窮舉法

比如一共3件商品,用0表示不取,1表示取,那麼就一共有

000 001 010

011 100 101

110 111

這樣方案,然後讓計算機去累加和,與重量上限比較,留下來的解里取最大即可。

2. 如何用遺傳演算法求解多重背包問題

遺傳演算法將目標函數轉換為適應度函數,評估,復制,交叉,變異種群中的個體,並從中選出適應性最強的個體,演算法的最優解就是這個個體。具體流程是:1.初始種群的產生。2.適應度函數的構造。3.選擇和繁殖。4.終止條件。

3. 遺傳演算法的一個問題

先在0到5中任選n個數,在將著n 個數轉換成二進制,然後存進一個數組A.定義一個函數f(x)(就是求x的四次方).定義循環次數為20次(可以自選).
1).計算A中每個數的函數制.(按十進制)
2).如果次數超過20,則取數組中最大的就是結果,演算法結束.
3).以一定概率選 A中k個最大的復制後加入數組,在刪除一些最小的,形成
數組A'
4).以一定概率選A'中若干二進制數進行交叉(既兩兩某些位互換),形成新
數組A''
5).以一定概率選A''中若干二進制數進行變異(即某些數的一些位發生反轉),
形成新數組A'''
6).將A'''做為A,轉步驟2.

4. 遺傳演算法可以解決什麼問題

遺傳演算法的應用比較廣泛,可用於解決數值優化、組合優化、機器學習、智能控制、人工生命、圖像處理、模式識別等領域的問題。比較具體多是:函數最值問題、旅行商問題、背包問題、車輛路徑問題、生產排程問題、選址問題等。

5. 怎麼使用遺傳演算法解決背包問題

樓主,能給點懸賞分嗎?給的話,我幫你找找程序。

6. 遺傳演算法具體應用

1、函數優化

函數優化是遺傳演算法的經典應用領域,也是遺傳演算法進行性能評價的常用算例,許多人構造出了各種各樣復雜形式的測試函數:連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。

2、組合優化

隨著問題規模的增大,組合優化問題的搜索空間也急劇增大,有時在目前的計算上用枚舉法很難求出最優解。對這類復雜的問題,人們已經意識到應把主要精力放在尋求滿意解上,而遺傳演算法是尋求這種滿意解的最佳工具之一。

此外,GA也在生產調度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

3、車間調度

車間調度問題是一個典型的NP-Hard問題,遺傳演算法作為一種經典的智能演算法廣泛用於車間調度中,很多學者都致力於用遺傳演算法解決車間調度問題,現今也取得了十分豐碩的成果。

從最初的傳統車間調度(JSP)問題到柔性作業車間調度問題(FJSP),遺傳演算法都有優異的表現,在很多算例中都得到了最優或近優解。


(6)遺傳演算法背包問題擴展閱讀:

遺傳演算法的缺點

1、編碼不規范及編碼存在表示的不準確性。

2、單一的遺傳演算法編碼不能全面地將優化問題的約束表示出來。考慮約束的一個方法就是對不可行解採用閾值,這樣,計算的時間必然增加。

3、遺傳演算法通常的效率比其他傳統的優化方法低。

4、遺傳演算法容易過早收斂。

5、遺傳演算法對演算法的精度、可行度、計算復雜性等方面,還沒有有效的定量分析方法。

7. 什麼是遺傳演算法

遺傳演算法是模擬自然界中按「優勝劣汰」法則進行進化過程而設計的演算法。Bagley和Rosengerg於1967年在他們的博士論文中首先提出了遺傳演算法的概念。1975年Holland出版的專著奠定了遺傳演算法的理論基礎。如今遺傳演算法不但給出了清晰的演算法描述,而且也建立了一些定量分析的結果,在眾多領域得到了廣泛的應用,如用於控制(煤氣管道的控制)、規劃(生產任務規劃)、設計(通信網路設計)、組合優化(TSP問題、背包問題)以及圖像處理和信號處理等。

8. 遺傳演算法求解背包問題的程序

1樓的不是遺傳演算法吧!
剛好做過這個遺傳演算法解背包問題的論文,給你回答啦~~獨家哦,分數要給偶~~

1、程序開發環境
開發環境:Visual C++6.0 (把Fortran程序改為VC)
操作系統:Windows 2003 Professional
2、程序性能對比
運行時間與加速比(如表1所示)
進程數p(個) 1 2 4
運行時間t(秒) 129s 78s 38s
加速比s 1.65 3.38
表1、運行時間與加速比
3、程序運行結果:
實例數據:
假設物體的重量Weight、物體的收益Profit和背包的容量Contain 分別為:
Weight={ 80,82,85,70,72, 70,66,50,55,25 ,
50,55,40,48,50, 32,22,60,30,32 ,
40,38,35,32,25, 28,30,22,50,30 ,
45,30,60,50,20 , 65,20,25,30,10 ,
20,25,15,10,10 , 10,4, 4, 2, 1 }
Profit={ 220,208,198,192,180, 180,165,162,160,158,
155,130,125,122,120 , 118,115,110,105,101,
100,100,98, 96, 95, 90, 88, 82, 80, 77 ,
75, 73, 72, 70, 69, 66, 65, 63, 60, 58,
56, 50, 30, 20, 15, 10, 8, 5, 3, 1}
Contain=1000,
如何選擇哪些物品裝入該背包可使得在背包的容量約束限制之內所裝物品的總價值最大?
傳統的演算法(動態規劃、遞歸回溯法和貪心演算法所得結果:
總價值為3077 , 總重量為999。
2001年張鈴,張鈸教授在計算機學報上發表的《佳點集遺傳演算法》所得結果
總價值為3103, 總重量為1000。
我們演算法所得結果: 總價值為3103, 總重量為1000。
我們所求得最優解的個體分配情況為:
11010 10111 10110 11011 01111 11101 00001 01001 10000
01000
演算法 最大迭代次數 總價值為 總重量為
傳統的演算法 400 3077 999
佳點集演算法 70 3103 1000
遺傳演算法 75 3103 1000

// knapsack.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <AfxWin.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>

// 重要常量參數
#define popsize 200 //種群的規模
#define pc 0.618 //雜交概率
#define pm 0.03 //變異概率
#define lchrom 50 //染色體長度
#define maxgen 1000 //最大進化代數

struct population
{
unsigned int chrom[lchrom]; //染色體
double weight; //背包重量
double fitness; //適應度
unsigned int parent1,parent2,cross; //雙親、交叉點
};

//新生代種群、父代種群
struct population oldpop[popsize],newpop[popsize];

//背包問題中物體重量、收益、背包容量
int weight[lchrom],profit[lchrom],contain;

//種群的總適應度、最小、最大、平均適應度
double sumfitness,minfitness,maxfitness,avgfitness;

//計算適應度時使用的 懲罰函數系數
double alpha;

//一個種群中最大和最小適應度的個體
int minpop,maxpop;

/* 讀入背包信息,並且計算懲罰函數系數 */
void read_infor()
{
FILE *fp;
int j;

//獲取背包問題信息文件
if ((fp=fopen("knapsack.txt","r"))==NULL)
{
//讀取文件失敗
AfxMessageBox("The file is not found",MB_OK,NULL);
return;
}
//讀入物體收益信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&profit[j]);
}
//讀入物體重量信息
for (j=0;j<lchrom;j++)
{
fscanf(fp,"%d",&weight[j]);
}
//讀入背包容量
fscanf(fp,"%d",&contain);
fclose(fp);

}

//根據計算的個體重量,判斷此個體是否該留在群體中
double cal_weight(unsigned int *chr)
{
int j;
double pop_weight;//背包重量

pop_weight=0;
for (j=0;j<lchrom;j++)
{
pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}
return pop_weight;
}

/* 種群中個體適應度計算*/
double cal_fit(unsigned int *chr)
{
int j;
double pop_profit;//適應度

pop_profit=0;
// pop_weight=0;

for (j=0;j<lchrom;j++)
{
pop_profit=pop_profit+(*chr)*profit[j];
// pop_weight=pop_weight+(*chr)*weight[j];
chr++;
}

return pop_profit;
}

/* 群體適應度的最大最小值以及其他信息 */
void statistics(struct population *pop)
{
int i;
double tmp_fit;

sumfitness=pop[0].fitness;
minfitness=pop[0].fitness;
minpop=0;
maxfitness=pop[0].fitness;
maxpop=0;

for (i=1;i<popsize;i++)
{
//計算種群的總適應度
sumfitness=sumfitness+pop[i].fitness;
tmp_fit=pop[i].fitness;
//選擇種群中最大適應度的個體
if ((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))
{
maxfitness=pop[i].fitness;
maxpop=i;
}

//選擇種群中最小適應度的個體
if (tmp_fit<minfitness)
{
minfitness=pop[i].fitness;
minpop=i;
}

//計算平均適應度
avgfitness=sumfitness/(float)popsize;
}
// printf("\nthe max pop = %d;",maxpop);
// printf("\nthe min pop = %d;",minpop);
// printf("\nthe sumfitness = %f\n",sumfitness);
}

//報告種群信息
void report(struct population *pop,int gen)
{
int j;
int pop_weight=0;

printf("the generation is %d.\n",gen); //輸出種群的代數
//輸出種群中最大適應度個體的染色體信息
printf("The population's chrom is: \n");
for (j=0;j<lchrom;j++)
{
if (j%5==0)
{ printf(" ");}
printf("%1d",pop[maxpop].chrom[j]);
}
//輸出群體中最大適應度
printf("\nThe population's max fitness is %d.",(int)pop[maxpop].fitness);
printf("\nThe knapsack weight is %d.\n\n",(int)pop[maxpop].weight);

}

/* 生成初始種群 */
void initpop()
{
int i,j,ispop;
double tmpWeight;
//變數用於判斷是否為滿足條件的個體
ispop=false;

//生成popsize個種群個體
for(i=0;i<popsize;i++)
{
while (!ispop)
{
for(j=0;j<lchrom;j++)
{
oldpop[i].chrom[j]=rand()%2; //隨機生成個體的染色體
oldpop[i].parent1=0; //雙親
oldpop[i].parent2=0;
oldpop[i].cross=0; //交叉點
}

//選擇重量小於背包容量的個體,即滿足條件
tmpWeight=cal_weight(oldpop[i].chrom);
if (tmpWeight<=contain)
{
oldpop[i].fitness=cal_fit(oldpop[i].chrom);
oldpop[i].weight=tmpWeight;
oldpop[i].parent1=0;
oldpop[i].parent2=0;
oldpop[i].cross=0;
ispop=true;
}
}
//此個體可以加入到種群中
ispop=false;
}
}

/* 遺傳操作 */

//概率選擇試驗
int execise(double probability)
{
double pp;
//如果生成隨機數大於相應的概率則返回真,否則試驗不成功
pp=(double)(rand()%20001/20000.0);
if (pp<=probability) return 1;
return 0;
}

// 選擇進行交叉操作的個體
int selection(int pop)
{
double wheel_pos,rand_Number,partsum;
int parent;

//賭輪法選擇
rand_Number=(rand()%2001)/2000.0;
wheel_pos=rand_Number*sumfitness; //賭輪大小

partsum=0;
parent=0;
do{
partsum=partsum+oldpop[parent].fitness;
parent=parent+1;
} while (partsum<wheel_pos && parent<popsize);
return parent-1;

}

/* 交叉操作 */
int crossover(unsigned int *parent1,unsigned int *parent2,int i)
{
int j,cross_pos;
if (execise(pc))
{
//生成交叉位置0,1,...(lchrom-2)
cross_pos=rand()%(lchrom-1);
}
else cross_pos=lchrom-1;

for (j=0;j<=cross_pos;j++)
{ //保留復制;
//包括在概率選擇不成功時,父體完全保留
newpop[i].chrom[j]=parent1[j];
}
for(j=cross_pos+1;j<=(lchrom-1);j++)
{
//從交叉點開始交叉
newpop[i].chrom[j]=parent2[j];
}

//記錄交叉位置
newpop[i].cross=cross_pos;
return 1;
}

/* 變異操作 */
int mutation(unsigned int alleles)
{
if (execise(pm))
{
if (alleles)
alleles=0;
else alleles=1;
}
//返回變異值,或者返回原值
return alleles;
}

/* 群體更新 */
void generation()
{
unsigned int i,j,mate1,mate2;
double tmpWeight;
int ispop;//記錄是否是符合條件的個體
i=0;
while (i<popsize)
{
ispop=false;
while (!ispop)
{
//選擇
mate1=selection(i);
mate2=selection(i+1);

//交叉
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i);

//變異
for (j=0;j<lchrom;j++)
{
newpop[i].chrom[j]=mutation(newpop[i].chrom[j]);
}

//選擇重量小於背包容量的個體,即滿足條件
tmpWeight=cal_weight(newpop[i].chrom);
if (tmpWeight<=contain)
{
newpop[i].fitness=cal_fit(newpop[i].chrom);
newpop[i].weight=tmpWeight;
newpop[i].parent1=mate1;
newpop[i].parent2=mate2;
ispop=true;
}
}
//此個體可以加入到種群中
i=i+1;
}
}

void main(int argc, char* argv[])
{
int gen,oldmaxpop,k;
double oldmax;

read_infor();//讀入背包信息
gen=0;
srand( (unsigned)time( NULL ) );//置隨機種子
initpop();
memcpy(&newpop,&oldpop,popsize*sizeof(struct population));
statistics(newpop);//統計新生種群的信息
report(newpop,gen);
while(gen<maxgen)
{
gen=gen+1;
if (gen%100==0)
{
srand( (unsigned)time( NULL ) );//置隨機種子
}
oldmax=maxfitness;
oldmaxpop=maxpop;
generation();
statistics(newpop); //統計新生代種群信息
//如果新生代種群中個體的最大適應度小於老一代種群
//個體的最大適應度,則保存老一代種群個體的最大適應度
//否則報告新生代的最大適應度
if (maxfitness<oldmax)
{
for(k=0;k<lchrom;k++)
newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k];
newpop[minpop].fitness=oldpop[oldmaxpop].fitness;
newpop[minpop].parent1=oldpop[oldmaxpop].parent1;
newpop[minpop].parent2=oldpop[oldmaxpop].parent2;
newpop[minpop].cross=oldpop[oldmaxpop].cross;
statistics(newpop);
}
else if (maxfitness>oldmax)
{
report(newpop,gen);
}

//保存新生代種群的信息到老一代種群信息空間
memcpy(&oldpop,&newpop,popsize*sizeof(struct population));
}

printf("It is over.");
getch();
}

9. 求助基於遺傳演算法的多選擇背包問題matlab程序

目標函數是使得資源均衡,滿足工序的合適開始時間即基因值
,困難是基因值不體現在目標函數的顯式表達式中,而是在約束條件中,不知道怎麼處理?
如果有哪位蟲友感興趣並願意提供幫助,將不勝感激!

熱點內容
如何用密碼鎖住並隱藏工作表 發布:2024-03-29 07:03:28 瀏覽:326
按鍵精靈滑鼠腳本 發布:2024-03-29 06:47:41 瀏覽:19
pythonhome 發布:2024-03-29 06:47:36 瀏覽:169
dns配置錯誤怎麼修理 發布:2024-03-29 06:36:15 瀏覽:980
電信客戶6位密碼是什麼 發布:2024-03-29 06:35:42 瀏覽:565
b星演算法找門 發布:2024-03-29 06:27:13 瀏覽:774
小數化分數c語言 發布:2024-03-29 06:20:16 瀏覽:561
如何搭建ai伺服器 發布:2024-03-29 06:20:10 瀏覽:493
用低配置手機玩游戲掉幀怎麼辦 發布:2024-03-29 06:20:06 瀏覽:588
安卓系統的微信如何安裝 發布:2024-03-29 05:48:45 瀏覽:993