深不可測(cè)的遺傳算法的原理原來(lái)是這么簡(jiǎn)單

很多人認(rèn)為，算法是數(shù)學(xué)的內(nèi)容，學(xué)起來(lái)特別麻煩。我們不能認(rèn)為這種觀點(diǎn)是錯(cuò)誤的。但是我們也知道，軟件是一種復(fù)合的技術(shù)，如果一個(gè)人只知道算法，但是不能用編程語(yǔ)言很好地實(shí)現(xiàn)，那么再優(yōu)秀的算法也不能發(fā)揮作用。

有一次，一個(gè)人問(wèn)我：

“你寫(xiě)的都是小兒科的東西，幾十行代碼就能搞定，能不能整一點(diǎn)高深的算法？”

我反問(wèn)他什么是他所理解的高深的算法，他答復(fù)說(shuō)：“像遺傳算法、蟻群算法之類(lèi)的?！庇谑俏医o了他一個(gè)遺傳算法求解0-1背包問(wèn)題的例子，并告訴他，這也就是幾十行代碼的算法，怎么理解成是高深的算法？他剛開(kāi)始不承認(rèn)這是遺傳算法，直到我給了他Denis Cormier公開(kāi)在北卡羅來(lái)納州立大學(xué)服務(wù)器上的遺傳算法的源代碼后，他才相信他一直認(rèn)為深不可測(cè)的遺傳算法的原理原來(lái)是這么簡(jiǎn)單。

還有一個(gè)人直言“用三個(gè)水桶等分8升水”之類(lèi)的問(wèn)題根本就稱(chēng)不上算法，他認(rèn)為像“阿法狗”那樣的人工智能才算是算法。我告訴他計(jì)算機(jī)下棋的基本理論就是博弈樹(shù)，或者再加一個(gè)專(zhuān)家系統(tǒng)。但是他認(rèn)為博弈樹(shù)也是很高深的算法，于是我給了他一個(gè)井字棋游戲，并告訴他，這就是博弈樹(shù)搜索算法，非常智能，你絕對(duì)戰(zhàn)勝不了它（因?yàn)榫制逵螒蚝芎?jiǎn)單，這個(gè)算法會(huì)把所有的狀態(tài)都搜索完）。我相信他一定很震驚，因?yàn)檫@個(gè)算法也不超過(guò)100行代碼。

對(duì)于上面提到的例子，我覺(jué)得主要原因在于大家對(duì)算法的理解有差異，很多人對(duì)算法的理解太片面，很多人覺(jué)得只有名字里包含“XX算法”之類(lèi)的東西才是算法。而我認(rèn)為算法的本質(zhì)是解決問(wèn)題，只要是能解決問(wèn)題的代碼就是算法。

一個(gè)人只有有了很好的計(jì)算機(jī)知識(shí)和數(shù)學(xué)知識(shí)，才能在算法的學(xué)習(xí)上不斷進(jìn)步。不管算法都么簡(jiǎn)單，都要自己親手實(shí)踐，只有不斷認(rèn)識(shí)錯(cuò)誤、不斷發(fā)現(xiàn)錯(cuò)誤，才能不斷提高自己的編程能力，不斷提高自己的業(yè)務(wù)水平。

其實(shí)任何算法都有自己的應(yīng)用環(huán)境和應(yīng)用場(chǎng)景，沒(méi)有算法可以適用于所有的場(chǎng)景。這一點(diǎn)希望大家明白。同時(shí)，我們也要清楚復(fù)雜的算法都是由普通的算法構(gòu)成的，沒(méi)有普通的算法就沒(méi)有復(fù)雜的算法可言，所以復(fù)雜變簡(jiǎn)單，由大化小，這就是算法分治遞歸的基本思想。

我們可以下面一個(gè)數(shù)組查找的函數(shù)說(shuō)起。一句一句講起，首先我們開(kāi)始從最簡(jiǎn)單的函數(shù)構(gòu)造開(kāi)始：

1.intfind(intarray[],intlength,intvalue)

2.{

3.intindex=0;

4.returnindex;

5.}

這里看到，查找函數(shù)只是一個(gè)普通的函數(shù)，那么首先需要判斷的就是參數(shù)的合法性：

1.staticvoidtest1()

2.{

3.intarray[10]={0};

4.assert(FALSE==find(NULL,10,10));

5.assert(FALSE==find(array,0,10));

6.}

這里可以看到，我們沒(méi)有判斷參數(shù)的合法性，那么原來(lái)的查找函數(shù)應(yīng)該怎么修改呢？

1.intfind(intarray[],intlength,intvalue)

2.{

3.if(NULL==array||0==length)

4.returnFALSE;

5.

6.intindex=0;

7.returnindex;

8.}

看到上面的代碼，說(shuō)明我們的已經(jīng)對(duì)入口參數(shù)進(jìn)行判斷了。那么下面就要開(kāi)始寫(xiě)代碼了。

1.intfind(intarray[],intlength,intvalue)

2.{

3.if(NULL==array||0==length)

4.returnFALSE;

5.

6.intindex=0;

7.for(;index

8.if(value==array[index])

9.returnindex;

10.}

11.

12.returnFALSE;

13.}

上面的代碼已經(jīng)接近完整了，那么測(cè)試用例又該怎么編寫(xiě)呢？

1.staticvoidtest2()

2.{

3.intarray[10]={1,2};

4.assert(0==find(array,10,1));

5.assert(FALSE==find(array,10,10));

6.}

運(yùn)行完所有的測(cè)試用例后，我們看看對(duì)原來(lái)的代碼有沒(méi)有什么可以?xún)?yōu)化的地方。其實(shí)，我們可以把數(shù)組轉(zhuǎn)變成指針。

1.intfind(intarray[],intlength,intvalue)

2.{

3.if(NULL==array||0==length)

4.returnFALSE;

5.

6.int*start=array;

7.int*end=array+length;

8.while(start

9.if(value==*start)

10.return((int)start-(int)array)/(sizeof(int));

11.start++;

12.}

13.

14.returnFALSE;

15.}

如果上面的代碼參數(shù)必須是通用的數(shù)據(jù)類(lèi)型呢？

1.template

2.intfind(typearray[],intlength,typevalue)

3.{

4.if(NULL==array||0==length)

5.returnFALSE;

6.

7.type*start=array;

8.type*end=array+length;

9.while(start

10.if(value==*start)

11.return((int)start-(int)array)/(sizeof(type));

12.start++;

13.}

14.

15.returnFALSE;

16.}

此時(shí)，測(cè)試用例是不是也需要重新修改呢？

1.staticvoidtest1()

2.{

3.intarray[10]={0};

4.assert(FALSE==find(NULL,10,10));

5.assert(FALSE==find(array,0,10));

6.}

7.

8.staticvoidtest2()

9.{

10.intarray[10]={1,2};

11.assert(0==find(array,10,1));

12.assert(FALSE==find(array,10,10));

13.}

最后，我們總結(jié)一下：

（1）我們的算法需要測(cè)試用例的驗(yàn)證

（2）任何的優(yōu)化都要建立在測(cè)試的基礎(chǔ)之上

（3）測(cè)試和代碼的編寫(xiě)要同步進(jìn)行

（4）算法的成功運(yùn)行時(shí)一步一步進(jìn)行得，每一步的成功必須確立在原有的成功之上