演算法是通法

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

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();
}

Ⅱ 何謂演算法演算法有什麼性質

演算法（algorithm），在數學（算學）和計算機科學之中，為任何一系列良定義的具體計算步驟，常用於計算、數據處理和自動推理。作為一個有效方法，演算法被用於計算函數，它包含了一系列定義清晰的指令，並可於有限的時間及空間內清楚的表述出來。

特點：

1、輸入：一個演算法必須有零個或以上輸入量。

2、輸出：一個演算法應有一個或以上輸出量，輸出量是演算法計算的結果。

3、明確性：演算法的描述必須無歧義，以保證演算法的實際執行結果是精確地符合要求或期望，通常要求實際運行結果是確定的。

4、有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統模擬的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必須在有限個步驟內完成任務。

5、有效性：又稱可行性。能夠實現，演算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現。

(2)演算法是通法擴展閱讀：

常用設計模式

完全遍歷法和不完全遍歷法：在問題的解是有限離散解空間，且可以驗證正確性和最優性時，最簡單的演算法就是把解空間的所有元素完全遍歷一遍，逐個檢測元素是否是我們要的解。

這是最直接的演算法，實現往往最簡單。但是當解空間特別龐大時，這種演算法很可能導致工程上無法承受的計算量。這時候可以利用不完全遍歷方法——例如各種搜索法和規劃法——來減少計算量。

1、分治法：把一個問題分割成互相獨立的多個部分分別求解的思路。這種求解思路帶來的好處之一是便於進行並行計算。

2、動態規劃法：當問題的整體最優解就是由局部最優解組成的時候，經常採用的一種方法。

3、貪心演算法：常見的近似求解思路。當問題的整體最優解不是（或無法證明是）由局部最優解組成，且對解的最優性沒有要求的時候，可以採用的一種方法。

4、簡並法：把一個問題通過邏輯或數學推理，簡化成與之等價或者近似的、相對簡單的模型，進而求解的方法。

Ⅲ 演算法有什麼用

問題一：提問！演算法到底有什麼用啊！ 學了數據結構了以後，就算偶們不說你也會知道演算法的重要。。。。
咱舉個非常簡單的例子，編一個比較n個數的大小並排列，但是用一般法、冒泡法、折半法.....各種不一樣的演算法效率是不一樣的。

詳情還是請仔細翻閱《數據結構》並把指針之類重要的內容全部搞清楚.....

做學問切勿心急，欲速而不達~~~~

問題二：在計算機中演算法有什麼作用？ 一個程序的核心在於演算法。比如說打開一個軟體和運行一個軟體的速度在計算機硬體性能相同情況下，軟體的演算法暢到了幾近決定性作用，所有的計算機軟體和硬體的編程都是需要演算法的，就算一個hello world程序雖然我們編時候沒有用到演算法但是在編譯他和運行再屏幕顯示的時候就是演算法了。演算法是計算機乃至自然界的核心，如果知道人腦的演算法，就可以製造出人工智慧的軟體。

問題三：編程演算法有什麼用？ 研究學習別人的演算法，能夠讓你散搏站在巨人的肩膀上思考問題。其實我們身邊無時不刻都在接觸演算法，一方面提高自身思考的能力，一方面可以提升代碼質量。
好的演算法不是晦澀難懂的，而是能夠讓人拍手稱奇的。

希望我的回答能對你有些許幫助，謹祝你成功！

問題四：學演算法分析到底有什麼用？ 其實你都說明白了，研究更高效的演算法就是為了節省時間。你學過數值分析么？你知道如過沒有高效的演算法,就按照矩陣的定義,來求20X20的矩陣,目前的電腦要算到地老天荒的。
API是哪來儲？你寫的那個能被sun採納么？如果都不研究排序演算法,那麼寫出來的代碼豈不跟你無異？

雲，聽說過吧？現在處理的數字,運算量已經超過了你的想像。一網路為例，每一天都處理的數據都是海量的，你要查個東西,沒幾秒就出來了，那不研究演算法,能行么。？

尤其是現在，數據越來越大，越來越多，演算法就顯得尤為重要了。

研究演算法，其實是鍛煉自己的思維。一個問題有不同的解決方式。當你碰到一個新的事物，你有可能寫得出演算法,單不一定能寫得出代碼。./question/422543292?oldq=1比如這個，我就是像想到演算法的乎掘團。

而且,敲代碼技術含量本身就不高，孰能生巧的過程。

問題五：研究計算機演算法對於編程有什麼作用？ 讓我來告訴你，演算法通俗意義上來講――就是解決一個問題的方法。據此而論，編寫程序解決的任何一個問題都可以歲橘叫做演算法。狹義上來講研究演算法就是在使用相同的計算資源的並解決同一個問題的情況下怎麼樣可以更加的節約資源，也就是說使計算速度更快。
拿一個例子來講就是排序，我們現在了解到的演算法有：冒泡，快速，插入，堆排序等等很多，在不同的輸入數據規模的情況下採用不同的演算法，因為可以節約計算資源。

問題六：學演算法有什麼用 其實你都說明白了，研究更高效的演算法就是為了節省時間。你學過數值分析么？你知道如過沒有高效的演算法,就按照矩陣的定義,來求20X20的矩陣,目前的電腦要算到地老天荒的。
API是哪來的？你寫的那個能被sun採納么？如果都不研究排序演算法,那麼寫出來的代碼豈不跟你無異？

雲，聽說過吧？現在處理的數字,運算量已經超過了你的想像。一網路為例，每一天都處理的數據都是海量的，你要查個東西,沒幾秒就出來了，那不研究演算法,能行么。？

尤其是現在，數據越來越大，越來越多，演算法就顯得尤為重要了。

研究演算法，其實是鍛煉自己的思維。一個問題有不同的解決方式。當你碰到一個新的事物，你有可能寫得出演算法,單不一定能寫得出代碼。./question/422543292?oldq=1比如這個，我就是像想到演算法的。

而且,敲代碼技術含量本身就不高，孰能生巧的過程。

問題七：演算法與編程有什麼關系? 演算法是通過編程來體現的

問題八：豎式計算有什麼作用 豎式的沿革沒有典籍記載 我國古代數學以計算為主,取得了十分輝煌的成就.其中十進位值制記數法、籌算和珠算在數學發展中所起的作用和顯示出來的優越性,在世界數學史上也是值得稱道的. 十進位值制記數法曾經被馬克思（1818―1883）稱為「最妙的發明之一」①. 從有文字記載開始,我國的記數法就遵循十進制.殷代的甲骨文和西周的鍾鼎文都是用一、二、三、四、五、六、七、八、九、十、百、千、萬等字的合文來記十萬以內的自然數的.例如二千六百五十六寫作■■■■（甲骨文）,六百五十九寫作■■■■■（鍾鼎文）.這種記數法含有明顯的位值制意義,實際上,只要把「千」、「百」、「十」和「又」的字樣取消,便和位值制記數法基本一樣了. 春秋戰國時期是我國從奴隸制轉變到封建制的時期,生產的迅速發展和科學技術的進步提出了大量比較復雜的數字計算問題.為了適應這種需要,勞動人民創造了一種十分重要的計算方法――籌算.我們認為籌算是完成於春秋戰國時期,理由是：第一,春秋戰國時期,農業、商業和天文歷法方面有了飛躍的發展,在這些領域中,出現了大量比以前復雜得多的計算問題.由於井田制的廢除,各種形狀的私田相繼出現,並相應實行按畝收稅的制度,這就需要計算復雜形狀的土地面積和產量；商業貿易的增加和貨幣的廣泛使用,提出了大量比例換算的問題；適應當時農業需要的厲法,要計算多位數的乘法和除法.為了解決這些復雜的計算問題,才創造出計算工具算籌和計算方法籌算.第二,現有的文獻和文物也證明籌算出現在春秋戰國時期.例如「算」和「籌」二字出現在春秋戰國時期的著作（如《儀禮》、《孫子》、《老子》、《法經》、《管子》、《荀子》等）中,甲骨文和鍾鼎文中到現在仍沒有見到這兩個字.一二三以外的籌算數字最早出現在戰國時期的貨幣（刀、布）上.《老子》提到：「善計者不用籌策」,可見這時籌算已經比較普遍了.因此我們說籌算是完成於春秋戰國時期.這並不否認在春秋戰國時期以前就有簡單的算籌記數和簡單的四則運算. 關於算籌形狀和大小,最早見於《漢書・律歷志》.

問題九：什麼叫演算法？什麼叫計算機演算法？ 演算法是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。演算法常常含有重復的步驟和一些比較或邏輯判斷。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法的時間復雜度是指演算法需要消耗的時間資源。一般來說，計算機演算法是問題規模n 的函數f(n)，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間復雜度（Asymptotic Time plexity）。時間復雜度用「O（數量級）」來表示，稱為「階」。常見的時間復雜度有： O（1）常數階；O（log2n）對數階；O（n）線性階；O（n2）平方階。

演算法的空間復雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間復雜度類似，一般都用復雜度的漸近性來表示。同時間復雜度相比，空間復雜度的分析要簡單得多。

[font class=Apple-style-span style=font-weight: bold; id=bks_etfhxykd]演算法 Algorithm [/font]

演算法是在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗點說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種演算法。前者是推理實現的演算法，後者是操作實現的演算法。

一個演算法應該具有以下五個重要的特徵：

1、有窮性： 一個演算法必須保證執行有限步之後結束；

2、確切性： 演算法的每一步驟必須有確切的定義；

3、輸入：一個演算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定除了初始條件；

4、輸出：一個演算法有一個或多個輸出，以反映對輸入數據加工後的結果。沒有輸出的演算法是毫無意義的；

5、可行性： 演算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算後即可完成。

演算法的設計要求

問題十：什麼是網路演算法？ 說的簡單點，就是指網路公司對於網站排名的一種計算公式。
從事SEO工作的人，想認識學習SEO，可以加群，群號前面137中間303後面464。特別是新手站長，沒有人指導的話，很容易走歪，自學SEO是比較難的，需要專業系統的學習。

2016網路搜索演算法大盤點

6月：打擊欺騙下載和無告知的捆綁下載。

7月：冰桶3.0，打擊移動頁強制用戶下載或調起APP的行為。

8月：天網，打擊網站竊取用戶信息，在網頁嵌惡意代碼，用於盜取網民的QQ號、手機號等隱私行為。

9月：冰桶4.0，網路搜索針對移動搜索結果頁廣告過多、影響用戶體驗的頁面，進行策略調整，冰桶演算法4.0特打擊此類站點。

11月：藍天，藍天演算法主要打擊新聞源站點售賣軟文、目錄行為。