| | yí chuán suàn fǎ （ geneticalgorithm） shì mó nǐ dá 'ěr wén de yí chuán xuǎn zé hé zì rán táo tài de shēng wù jìn huà guò chéng de jì suàn mó xíng， shì yī zhǒng tōng guò mó nǐ zì rán jìn huà guò chéng sōu suǒ zuì yōu jiě de fāng fǎ， tā shì yòu měi guó michigan dà xué j.holland jiào shòu yú 1975 nián shǒu xiān tí chū lái de， bìng chū bǎn liǎo pō yòu yǐng xiǎng de zhuān zhù《 adaptationinnaturalandartificialsystems》， ga zhè gè míng chēng cái zhú jiàn wéi rén suǒ zhī， j.hilland jiào shòu suǒ tí chū de ga tōng cháng wéi jiǎn dān yí chuán suàn fǎ （ sga）。
yí chuán suàn fǎ shì cóng dài biǎo wèn tí kě néng qián zài de jiě jí de yī gè zhǒng qún（ population） kāi shǐ de， ér yī gè zhǒng qún zé yóu jīng guò jī yīn（ gene） biān mǎ de yī dìng shù mùdì gè tǐ (individual) zǔ chéng。 měi gè gè tǐ shí jì shàng shì rǎn sè tǐ (chromosome) dài yòu tè zhēng de shí tǐ。 rǎn sè tǐ zuò wéi yí chuán wù zhì de zhù yào zài tǐ， jí duō gè jī yīn de jí hé， qí nèi bù biǎo xiàn（ jí jī yīn xíng） shì mǒu zhǒng jī yīn zǔ hé， tā jué dìng liǎo gè tǐ de xíng zhuàng de wài bù biǎo xiàn， rú hēi tóu fā de tè zhēng shì yóu rǎn sè tǐ zhōng kòng zhì zhè yī tè zhēng de mǒu zhǒng jī yīn zǔ hé jué dìng de。 yīn cǐ， zài yī kāi shǐ xū yào shí xiàn cóng biǎo xiàn xíng dào jī yīn xíng de yìng shè jí biān mǎ gōng zuò。 yóu yú fǎng zhào jī yīn biān mǎ de gōng zuò hěn fù zá， wǒ men wǎng wǎng jìn xíng jiǎn huà， rú 'èr jìn zhì biān mǎ， chū dài zhǒng qún chǎn shēng zhī hòu， àn zhào shì zhě shēng cún hé yōu shèng liè tài de yuán lǐ， zhú dài（ generation） yǎn huà chǎn shēng chū yuè lái yuè hǎo de jìn sì jiě， zài měi yī dài， gēn jù wèn tí yù zhōng gè tǐ de shì yìng dù（ fitness） dà xiǎo tiǎo xuǎn（ _select_ion） gè tǐ， bìng jiè zhù yú zì rán yí chuán xué de yí chuán suàn zǐ（ geneticoperators） jìn xíng zǔ hé jiāo chā（ crossover） hé biàn yì（ mutation）， chǎn shēng chū dài biǎo xīn de jiě jí de zhǒng qún。 zhè gè guò chéng jiāng dǎo zhì zhǒng qún xiàng zì rán jìn huà yī yàng de hòu shēng dài zhǒng qún bǐ qián dài gèng jiā shì yìng yú huán jìng， mò dài zhǒng qún zhōng de zuì yōu gè tǐ jīng guò jiě mǎ（ decoding）， kě yǐ zuò wéi wèn tí jìn sì zuì yōu jiě。 | | yí chuán suàn fǎ shì yī lèi kě yòng yú fù zá xì tǒng yōu huà de jù yòu lǔ bàng xìng de sōu suǒ suàn fǎ， yǔ chuán tǒng de yōu huà suàn fǎ xiāng bǐ， zhù yào yòu yǐ xià tè diǎn：
1、 yí chuán suàn fǎ yǐ jué cè biàn liàng de biān mǎ zuò wéi yùn suàn duì xiàng。 chuán tǒng de yōu huà suàn fǎ wǎng wǎng zhí jiē jué cè biàn liàng de shí jì zhí běn shēn， ér yí chuán suàn fǎ chǔlǐ jué cè biàn liàng de mǒu zhǒng biān mǎ xíng shì， shǐ dé wǒ men kě yǐ jiè jiàn shēng wù xué zhōng de rǎn sè tǐ hé jī yīn de gài niàn， kě yǐ mó fǎng zì rán jiè shēng wù de yí chuán hé jìn huà jī lǐ， yě shǐ dé wǒ men néng gòu fāng biàn de yìng yòng yí chuán cāo zuò suàn zǐ。
2、 yí chuán suàn fǎ zhí jiē yǐ shì yìng dù zuò wéi sōu suǒ xìn xī， wú xū dǎo shù děng qí tā fǔ zhù xìn xī。
3、 yí chuán suàn fǎ shǐ yòng duō gè diǎn de sōu suǒ xìn xī， jù yòu yǐn hán bìng xíng xìng。
4、 yí chuán suàn fǎ shǐ yòng gàilǜ sōu suǒ jì shù， ér fēi què dìng xìng guī zé。 | yí chuán suàn fǎ de yìng yòng | yóu yú yí chuán suàn fǎ de zhěng tǐ sōu suǒ cè lüè hé yōu huà sōu suǒ fāng fǎ zài jì suàn shì bù yǐ lài yú tī dù xìn xī huò qí tā fǔ zhù zhī shí， ér zhǐ xū yào yǐng xiǎng sōu suǒ fāng xiàng de mù biāo hán shù hé xiāng yìng de shì yìng dù hán shù， suǒ yǐ yí chuán suàn fǎ tí gōng liǎo yī zhǒng qiú jiě fù zá xì tǒng wèn tí de tōng yòng kuàng jià， tā bù yǐ lài yú wèn tí de jù tǐ lǐng yù， duì wèn tí de zhǒng lèi yòu hěn qiáng de lǔ bàng xìng， suǒ yǐ guǎng fàn yìng yòng yú xǔ duō kē xué， xià miàn wǒ men jiāng jiè shào yí chuán suàn fǎ de yī xiē zhù yào yìng yòng lǐng yù：
1、 hán shù yōu huà。
hán shù yōu huà shì yí chuán suàn fǎ de jīng diǎn yìng yòng lǐng yù， yě shì yí chuán suàn fǎ jìn xíng xìng néng píng jià de cháng yòng suàn lì， xǔ duō rén gòu zào chū liǎo gè zhǒng gè yàng fù zá xíng shì de cè shì hán shù： lián xù hán shù hé lí sàn hán shù、 tū hán shù hé 'āo hán shù、 dī wéi hán shù hé gāo wéi hán shù、 dān fēng hán shù hé duō fēng hán shù děng。 duì yú yī xiē fēi xiàn xìng、 duō mó xíng、 duō mù biāo de hán shù yōu huà wèn tí， yòng qí tā yōu huà fāng fǎ jiào nán qiú jiě， ér yí chuán suàn fǎ kě yǐ fāng biàn de dé dào jiào hǎo de jiēguǒ。
2、 zǔ hé yōu huà
suí zhe wèn tí guī mó de zēng dà， zǔ hé yōu huà wèn tí de sōu suǒ kōng jiān yě jí jù zēng dà， yòu shí zài mù qián de jì suàn shàng yòng méi jǔ fǎ hěn nán qiú chū zuì yōu jiě。 duì zhè lèi fù zá de wèn tí， rén men yǐ jīng yì shí dào yìng bǎ zhù yào jīng lì fàng zài xún qiú mǎn yì jiě shàng， ér yí chuán suàn fǎ shì xún qiú zhè zhǒng mǎn yì jiě de zuì jiā gōng jù zhī yī。 shí jiàn zhèng míng， yí chuán suàn fǎ duì yú zǔ hé yōu huà zhōng de np wèn tí fēi cháng yòu xiào。 lì rú yí chuán suàn fǎ yǐ jīng zài qiú jiě lǚ xíng shāng wèn tí、 bēibāo wèn tí、 zhuāng xiāng wèn tí、 tú xíng huàfēn wèn tí děng fāng miàn dé dào chéng gōng de yìng yòng。
cǐ wài， ga yě zài shēng chǎn diào dù wèn tí、 zì dòng kòng zhì、 jī qì rén xué、 tú xiàng chǔlǐ、 rén gōng shēng mìng、 yí chuán biān mǎ hé jī qì xué xí děng fāng miàn huò dé liǎo guǎng fàn de yùn yòng。 | yí chuán suàn fǎ de xiàn zhuàng | jìn rù 90 nián dài， yí chuán suàn fǎ yíng lái liǎo xīng shèng fā zhǎn shí qī， wú lùn shì lǐ lùn yán jiū hái shì yìng yòng yán jiū dōuchéng liǎo shí fēn rè mén de kè tí。 yóu qí shì yí chuán suàn fǎ de yìng yòng yán jiū xiǎn dé gé wài huó yuè， bù dàn tā de yìng yòng lǐng yù kuò dà， ér qiě lì yòng yí chuán suàn fǎ jìn xíng yōu huà hé guī zé xué xí de néng lì yě xiǎn zhù tí gāo， tóng shí chǎn yè yìng yòng fāng miàn de yán jiū yě zài mō suǒ zhī zhōng。 cǐ wài yī xiē xīn de lǐ lùn hé fāng fǎ zài yìng yòng yán jiū zhōng yì dé dào liǎo xùn sù de fā zhǎn， zhè xiē wú yí jūn gěi yí chuán suàn fǎ zēng tiān liǎo xīn de huó lì。 yí chuán suàn fǎ de yìng yòng yán jiū yǐ cóng chū qī de zǔ hé yōu huà qiú jiě kuò zhǎn dào liǎo xǔ duō gēngxīn、 gèng gōng chéng huà de yìng yòng fāng miàn。
suí zhe yìng yòng lǐng yù de kuò zhǎn， yí chuán suàn fǎ de yán jiū chū xiàn liǎo jǐ gè yǐn rén zhù mùdì xīn dòng xiàng： yī shì jī yú yí chuán suàn fǎ de jī qì xué xí， zhè yī xīn de yán jiū kè tí bǎ yí chuán suàn fǎ cóng lì lái lí sàn de sōu suǒ kōng jiān de yōu huà sōu suǒ suàn fǎ kuò zhǎn dào jù yòu dú tè de guī zé shēng chéng gōng néng de zhǎn xīn de jī qì xué xí suàn fǎ。 zhè yī xīn de xué xí jī zhì duì yú jiě jué rén gōng zhì néng zhōng zhī shí huò qǔ hé zhī shí yōu huà jīng liàn de píng jǐng nán tí dài lái liǎo xī wàng。 èr shì yí chuán suàn fǎ zhèng rì yì hé shén jīng wǎng luò、 mó hú tuī lǐ yǐ jí hùn dùn lǐ lùn děng qí tā zhì néng jì suàn fāng fǎ xiāng hù shèn tòu hé jié hé， zhè duì kāi tuò 21 shì jì zhōng xīn de zhì néng jì suàn jì shù jiāng jù yòu zhòng yào de yì yì。 sān shì bìng xíng chǔlǐ de yí chuán suàn fǎ de yán jiū shí fēn huó yuè。 zhè yī yán jiū bù jǐn duì yí chuán suàn fǎ běn shēn de fā zhǎn， ér qiě duì yú xīn yī dài zhì néng jì suàn jī tǐ jìjié gòu de yán jiū dōushì shí fēn zhòng yào de。 sì shì yí chuán suàn fǎ hé lìng yī gè chēng wéi rén gōng shēng mìng de zhǎn xīn yán jiū lǐng yù zhèng bù duàn shèn tòu。 suǒ wèi rén gōng shēng mìng jí shì yòng jì suàn jī mó nǐ zì rán jiè fēng fù duō cǎi de shēng mìng xiàn xiàng， qí zhōng shēng wù de zì shì yìng、 jìn huà hé miǎn yì děng xiàn xiàng shì rén gōng shēng mìng de zhòng yào yán jiū duì xiàng， ér yí chuán suàn fǎ zài zhè fāng miàn jiāng huì fā huī yī dìng de zuò yòng， wǔ shì yí chuán suàn fǎ hé jìn huà guī huá（ evolutionprogramming,ep） yǐ jí jìn huà cè lüè（ evolutionstrategy,es） děng jìn huà jì suàn lǐ lùn rì yì jié hé。 ep hé es jīhū shì hé yí chuán suàn fǎ tóng shí dú lì fā zhǎn qǐ lái de， tóng yí chuán suàn fǎ yī yàng， tā men yě shì mó nǐ zì rán jiè shēng wù jìn huà jī zhì de zhǐ néng jì suàn fāng fǎ， jí tóng yí chuán suàn fǎ jù yòu xiāng tóng zhī chù， yě yòu gè zì de tè diǎn。 mù qián， zhè sān zhě zhī jiān de bǐ jiào yán jiū hé bǐ cǐ jié hé de tàn tǎo zhèng xíng chéng rè diǎn。
1991 nián d.whitey zài tā de lùn wén zhōng tí chū liǎo jī yú lǐng yù jiāo chā de jiāo chā suàn zǐ（ adjacencybasedcrossover）， zhè gè suàn zǐ shì tè bié zhēn duì yòng xù hào biǎo shì jī yīn de gè tǐ de jiāo chā， bìng jiāng qí yìng yòng dào liǎo tsp wèn tí zhōng， tōng guò shí yàn duì qí jìn xíng liǎo yàn zhèng。
d.h.ackley děng tí chū liǎo suí jí dié dài yí chuán pá shān fǎ（ stochasticiteratedgenetichill-climbing， sigh） cǎi yòng liǎo yī zhǒng fù zá de gàilǜ xuǎn jǔ jī zhì， cǐ jī zhì zhōng yóu m gè “ tóu piào zhě ” lái gòng tóng jué dìng xīn gè tǐ de zhí（ m biǎo shì qún tǐ de dà xiǎo）。 shí yàn jiēguǒ biǎo míng， sigh yǔ dān diǎn jiāo chā、 jūn yún jiāo chā de shén jīng yí chuán suàn fǎ xiāng bǐ， suǒ cè shì de liù gè hán shù zhōng yòu sì gè biǎo xiàn chū gèng hǎo de xìng néng， ér qiě zǒng tǐ lái jiǎng， sigh bǐ xiàn cún de xǔ duō suàn fǎ zài qiú jiě sù dù fāng miàn gèng yòu jìng zhēng lì。
h.bersini hé g.seront jiāng yí chuán suàn fǎ yǔ dān yī fāng fǎ（ simplexmethod） jié hé qǐ lái， xíng chéng liǎo yī zhǒng jiào dān yī cāo zuò de duō qīn jiāo chā suàn zǐ（ simplexcrossover）， gāi suàn zǐ zài gēn jù liǎng gè mǔ tǐ yǐ jí yī gè 'é wài de gè tǐ chǎn shēng xīn gè tǐ， shì shí shàng tā de jiāo chā jiēguǒ yǔ duì sān gè gè tǐ yòng xuǎn jǔ jiāo chā chǎn shēng de jiēguǒ yī zhì。 tóng shí， wén xiàn hái jiāng sān zhě jiāo chā suàn zǐ yǔ diǎn jiāo chā、 jūn yún jiāo chā zuò liǎo bǐ jiào， jiēguǒ biǎo míng， sān zhè jiāo chā suàn zǐ bǐ qí yú liǎng gè yòu gèng hǎo de xìng néng。
guó nèi yě yòu bù shǎo de zhuān jiā hé xué zhě duì yí chuán suàn fǎ de jiāo chā suàn zǐ jìn xíng gǎi jìn。 2002 nián， dài xiǎo míng děng yìng yòng duō zhǒng qún yí chuán bìng xíng jìn huà de sī xiǎng， duì bù tóng zhǒng qún jī yú bù tóng de yí chuán cè lüè， rú biàn yì gàilǜ， bù tóng de biàn yì suàn zǐ děng lái sōu suǒ biàn liàng kōng jiān， bìng lì yòng zhǒng qún jiān qiān yí suàn zǐ lái jìn xíng yí chuán xìn xī jiāo liú， yǐ jiě jué jīng diǎn yí chuán suàn fǎ de shōu liǎn dào jú bù zuì yōu zhí wèn tí
2004 nián， zhào hóng lì děng zhēn duì jiǎn dān yí chuán suàn fǎ zài jiào dà guī mó zǔ hé yōu huà wèn tí shàng sōu suǒ xiàolǜ bù gāo de xiàn xiàng， tí chū liǎo yī zhǒng yòng jī yīn kuài biān mǎ de bìng xíng yí chuán suàn fǎ （ building-blockcodedparallelga， bcpga）。 gāi fāng fǎ yǐ cū lì dù bìng xíng yí chuán suàn fǎ wéi jī běn kuàng jià， zài rǎn sè tǐ qún tǐ zhōng shí bié chū kě néng de jī yīn kuài， rán hòu yòng jī yīn kuài zuò wéi xīn de jī yīn dān wèi duì rǎn sè tǐ chóngxīn biān mǎ， chǎn shēng cháng dù jiào duǎn de rǎn sè tǐ， zài yòng chóngxīn biān mǎ de rǎn sè tǐ qún tǐ zuò wéi xià yī lún yǐ xiāng tóng fāng shì yǎn huà de chū shǐ qún tǐ。
2005 nián， jiāng léi děng zhēn duì bìng xíng yí chuán suàn fǎ qiú jiě tsp wèn tí , tàn tǎo liǎo shǐ yòng tánxìng cè lüè lái wéi chí qún tǐ de duō yàng xìng , shǐ dé suàn fǎ kuà guò jú bù shōu liǎn de zhàng 'ài , xiàng quán jú zuì yōu jiě fāng xiàng jìn huà。 | yí chuán suàn fǎ de yī bān suàn fǎ | yí chuán suàn fǎ shì jī yú shēng wù xué de， lǐ jiě huò biān chéng dōubù tài nán。 xià miàn shì yí chuán suàn fǎ de yī bān suàn fǎ：
lù lù chuàng jiàn yī gè suí jī de chū shǐ zhuàng tài
lù lù chū shǐ zhǒng qún shì cóng jiě zhōng suí jī xuǎn zé chū lái de， jiāng zhè xiē jiě bǐ yù wéi rǎn sè tǐ huò jī yīn， gāi zhǒng qún bèi chēng wéi dì yī dài， zhè hé fú hào rén gōng zhì néng xì tǒng de qíng kuàng bù yī yàng， zài nà lǐ wèn tí de chū shǐ zhuàng tài yǐ jīng gěi dìng liǎo。
lù lù píng gū shì yìng dù
lù lù duì měi yī gè jiě ( rǎn sè tǐ ) zhǐ dìng yī gè shì yìng dù de zhí， gēn jù wèn tí qiú jiě de shí jì jiē jìn chéng dù lái zhǐ dìng ( yǐ biàn bī jìn qiú jiě wèn tí de dá 'àn )。 bù yào bǎ zhè xiē“ jiě” yǔ wèn tí de“ dá 'àn” hùn wéi yī tán， kě yǐ bǎ tā lǐ jiě chéng wéi yào dé dào dá 'àn， xì tǒng kě néng xū yào lì yòng de nà xiē tè xìng。
lù lù fán zhí ( bāo kuò zǐ dài tū biàn )
lù lù dài yòu jiào gāo shì yìng dù zhí de nà xiē rǎn sè tǐ gèng kě néng chǎn shēng hòu dài ( hòu dài chǎn shēng hòu yě jiāng fā shēng tū biàn )。 hòu dài shì fù mǔ de chǎn wù， tā men yóu lái zì fù mǔ de jī yīn jié hé 'ér chéng， zhè gè guò chéng bèi chēng wéi“ zá jiāo”。
lù lù xià yī dài
lù lù rú guǒ xīn de yī dài bāo hán yī gè jiě， néng chǎn shēng yī gè chōng fēn jiē jìn huò děng yú qī wàng dá 'àn de shū chū， nà me wèn tí jiù yǐ jīng jiě jué liǎo。 rú guǒ qíng kuàng bìng fēi rú cǐ， xīn de yī dài jiāng chóngfù tā men fù mǔ suǒ jìn xíng de fán yǎn guò chéng， yī dài yī dài yǎn huà xià qù， zhí dào dá dào qī wàng de jiě wéi zhǐ。
lù lù bìng xíng jì suàn
lù lù fēi cháng róng yì jiāng yí chuán suàn fǎ yòng dào bìng xíng jì suàn hé qún jí huán jìng zhōng。 yī zhǒng fāng fǎ shì zhí jiē bǎ měi gè jié diǎn dàngchéng yī gè bìng xíng de zhǒng qún kàn dài。 rán hòu yòu jī tǐ gēn jù bù tóng de fán zhí fāng fǎ cóng yī gè jié diǎn qiān yí dào lìng yī gè jié diǎn。 lìng yī zhǒng fāng fǎ shì“ nóng chǎng zhù / láo gōng” tǐ xì jié gòu， zhǐ dìng yī gè jié diǎn wéi“ nóng chǎng zhù” jié diǎn， fù zé xuǎn zé yòu jī tǐ hé fēn pài shì yìng dù de zhí， lìng wài de jié diǎn zuò wéi“ láo gōng” jié diǎn， fù zé chóngxīn zǔ hé、 biàn yì hé shì yìng dù hán shù de píng gū。
shù yǔ shuō míng
yóu yú yí chuán suàn fǎ shì yóu jìn huà lùn hé yí chuán xué jī lǐ 'ér chǎn shēng de sōu suǒ suàn fǎ， suǒ yǐ zài zhè gè suàn fǎ zhōng huì yòng dào hěn duō shēng wù yí chuán xué zhī shí， xià miàn shì wǒ men jiāng huì yòng lái de yī xiē shù yǔ shuō míng：
yī、 rǎn sè tǐ (chronmosome)
rǎn sè tǐ yòu kě yǐ jiào zuò jī yīn xíng gè tǐ (individuals), yī dìng shù liàng de gè tǐ zǔ chéng liǎo qún tǐ (population), qún tǐ zhōng gè tǐ de shù liàng jiào zuò qún tǐ dà xiǎo。
èr、 jī yīn (gene)
jī yīn shì chuàn zhōng de yuán sù， jī yīn yòng yú biǎo shì gè tǐ de tè zhēng。 lì rú yòu yī gè chuàn s ＝ 1011， zé qí zhōng de 1， 0， 1， 1 zhè 4 gè yuán sù fēn bié chēng wéi jī yīn。 tā men de zhí chēng wéi děng wèi jī yīn (alletes)。
sān、 jī yīn dì diǎn (locus)
jī yīn dì diǎn zài suàn fǎ zhōng biǎo shì yī gè jī yīn zài chuàn zhōng de wèi zhì chēng wéi jī yīn wèi zhì (geneposition)， yòu shí yě jiǎn chēng jī yīn wèi。 jī yīn wèi zhì yóu chuàn de zuǒ xiàng yòu jì suàn， lì rú zài chuàn s＝ 1101 zhōng， 0 de jī yīn wèi zhì shì 3。
sì、 jī yīn tè zhēng zhí (genefeature)
zài yòng chuàn biǎo shì zhěng shù shí， jī yīn de tè zhēng zhí yǔ 'èr jìn zhì shù de quán yī zhì； lì rú zài chuàn s=1011 zhōng， jī yīn wèi zhì 3 zhōng de 1， tā de jī yīn tè zhēng zhí wéi 2； jī yīn wèi zhì 1 zhōng de 1， tā de jī yīn tè zhēng zhí wéi 8。
wǔ、 shì yìng dù (fitness)
gè gè gè tǐ duì huán jìng de shì yìng chéng dù jiào zuò shì yìng dù (fitness)。 wèile tǐ xiàn rǎn sè tǐ de shì yìng néng lì， yǐn rù liǎo duì wèn tí zhōng de měi yī gè rǎn sè tǐ dōunéng jìn xíng dù liàng de hán shù， jiào shì yìng dù hán shù . zhè gè hán shù shì jì suàn gè tǐ zài qún tǐ zhōng bèi shǐ yòng de gàilǜ。 | | --------- lái gè lì zǐ， dà jiā hǎo lǐ jiě ------------
jī yú yí chuán suàn fǎ de rén gōng shēng mìng mó nǐ
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<math.h>
#include<time.h>
#include<string.h>
#include"graph.c"
/* hóng dìng yì */
#definetl120/* zhí wù xìng shí wù xiàn zhì shí jiān */
#definetl25/* dòng wù xìng shí wù xiàn zhì shí jiān */
#definenewfoods3/* zhí wù xìng shí wù měi dài shēng chéng shù mù */
#definemutation0.05/* biàn yì gàilǜ */
#defineg_length32/* gè tǐ rǎn sè tǐ cháng dù */
#definemax_pop100/* gè tǐ zǒng shù de zuì dà zhí */
#definemax_food100/* shí wù zǒng shù de zuì dà zhí */
#definemax_wx60/* xū nǐ huán jìng de cháng dù zuì dà zhí */
#definemax_wy32/* xū nǐ huán jìng de kuān dù zuì dà zhí */
#definesx1330/* xū nǐ huán jìng tú zuǒ shàng jiǎo diǎn x zuò biāo */
#definesy140/* xū nǐ huán jìng tú zuǒ shàng jiǎo diǎn y zuò biāo */
#definegx360/* gè tǐ shù jìn huà tú xíng chuāng kǒu de zuǒ shàng jiǎo diǎn x zuò biāo */
#definegy257/* gè tǐ shù jìn huà tú xíng chuāng kǒu de zuǒ shàng jiǎo diǎn y zuò biāo */
#definegxr250/* gè tǐ shù jìn huà tú xíng chuāng kǒu de cháng dù */
#definegyr100/* gè tǐ shù jìn huà tú xíng chuāng kǒu de kuān dù */
#definegstep2/* gè tǐ shù jìn huà tú xíng chuāng kǒu de x fāng xiàng bù cháng */
#definer_life0.05/* chū qī chǎn shēng shēng wù shù de huán jìng bǐlǜ */
#definer_food0.02/* chū qī chǎn shēng shí wù shù de huán jìng bǐlǜ */
#definesl_min10/* gè tǐ shòu mìng zuì xiǎo zhí */
/* quán jú biàn liàng */
unsignedchargene[max_pop][g_length];/* yí chuán jī yīn */
unsignedchariflg[max_pop];/* gè tǐ sǐ huó zhuàng tài biāo zhì biàn liàng */
unsignedcharfflg[max_food];/* shí wù yòu wú zhuàng tài biāo zhì biàn liàng */
unsignedcharworld[max_wx][max_wy];/* xū nǐ huán jìng de shù jù */
unsignedchar/* gè zhōng xíng wéi mó shì shù jù */
life1={{0,0,1,0,0},{0,1,0,1,0},{1,0,0,0,1},{0,1,0,1,0},{0,0,1,0,0}};
unsignedchar
life2={{1,1,1,1,1},{1,0,0,0,1},{1,0,0,0,1},{1,0,0,0,1},{1,1,1,1,1}};
unsignedchar
food1={{0,0,0,1,0},{0,0,1,1,0},{0,1,0,1,0},{0,0,1,1,0},{0,0,0,1,0}};
unsignedchar
food2={{0,0,0,1,0},{0,0,1,1,0},{0,1,1,1,0},{0,0,1,1,0},{0,0,0,1,0}};
intpop_size;/* gè tǐ zǒng shù */
intiatr[max_pop];/* gè tǐ shǔ xìng */
/*iatr[][0] gè tǐ dāng qián wèi zhì x zuò biāo */
/*iatr[] gè tǐ dāng qián wèi zhì y zuò biāo */
/*iatr[] nèi bù néng liàng */
/*iatr[] nián líng shǔ xìng */
intfood_size;/* shí wù zǒng shù */
intfatr[max_food];/* shí wù shǔ xìng */
/*fatr[][0] shí wù dāng qián wèi zhì x zuò biāo */
/*fatr[] shí wù dāng qián wèi zhì y zuò biāo */
/*fatr[]=0: zhí wù xìng =1: dòng wù xìng */
/*fatr[] xīn xiān chéng dù */
intwx,wy;/* xū nǐ huán jìng de cháng kuān dù */
voiduni_crossover(gene,g1,g2,g3,ratio1,g_length)/* jūn yún jiāo chā */
unsignedchar*gene;/* yí chuán jī yīn */
intg1,g2,g3;/*g1g2 fù gè tǐ biān hào g3 zǐ gè tǐ biān hào */
doubleratio1;/* fù gè tǐ g1 bèi xuǎn zhōng de gàilǜ */
intg_length;/* gè tǐ yí chuán jī yīn de wèi cháng */
{
unsignedchar*gene1;/* fù 1 yí chuán jī yīn de zhǐ zhēn */
unsignedchar*gene2;/* fù 2 yí chuán jī yīn de zhǐ zhēn */
unsignedchar*gene3;/* zǐ yí chuán jī yīn de zhǐ zhēn */
doublernd,r1;
inti;
gene1=gene+g_length*g1;
gene2=gene+g_length*g2;
gene3=gene+g_length*g3;
r1=(int)(10000.0*ratio1);
for(i=0;i<g_length;i++)
{rnd=random(10000);
if(rnd<=r1)*(gene3+i)=*(gene1+i);
else*(gene3+i)=*(gene2+i);
}
}
voidg_disp_unit(x,y,n)
/* huì zhì xū nǐ huán jìng de yī gè dān yuán */
intx,y;/*x=0,1,2....,wx-1;y=0,1,2,....,wy-1*/
intn;/*n=0:=1: shēng wù 1=2: shēng wù 2=3: zhí wù xìng shí wù =4: zhàng 'ài wù =5: dòng wù xìng shí wù */
{
intgx,gy,i,j;
unsignedcharcol;
gx=sx1+5*x;gy=sy1+5*y;
for(i=0;i<5;i++)
for(j=0;j<5;j++)
{switch(n)
{case0:col=0;break;
case1:col=life1[j][i]*2;break;
case2:col=life2[j][i]*4;break;
case3:col=food1[j][i]*6;break;
case4:col=7;break;
case5:col=food2[j][i]*11;
}
g_pset(gx+j,gy+i,col);
}
}
voidg_draw_world()/* xiǎn shì xū nǐ huán jìng huà miàn */
{
inti,j;
for(i=0;i<wy;i++)
for(j=0;j<wx;j++)
g_disp_unit(j,i,world[j][i]);
}
voidg_draw_frame(x1,y1,x2,y2,c1,c2,c3,c4,text)
intx1,y1,x2,y2,c1,c2,c3,c4;
char*text;
{intn,x3;
g_rectangle(x1,y1,x2,y2,c1,1);
g_rectangle(x1,y1,x2,y2,c2,0);
g_rectangle(x1,y1,x2,y1+16,c3,1);
g_rectangle(x1,y1,x2,y1+16,c2,0);
n=strlen(text);
x3=x1+((x2-x1-n*8)/2);
disp_hz16(text,x3,y1,c4);
}
voidg_init_frames()/* chū shǐ huà huà miàn */
{
inti,j,cx,cy,x,y;
chartext;
g_draw_frame(0,0,639,399,15,0,4,15,
" jī yú yí chuán suàn fǎ de rén gōng shēng mìng mó nǐ ");
g_draw_frame(0,16,320,170,7,0,8,15," shè dìng cān shù ");
y=48;
setcolor(9);
disp_hz16(" zhí wù shí wù xiàn zhì shí jiān ",16,y,15);
sprintf(text,"%d",tl1);
g_text(200,y+8,4,text);
y=y+24;
setcolor(9);
disp_hz16(" dòng wù shí wù xiàn zhì shí jiān ",16,y,15);
sprintf(text,"%d",tl2);
g_text(200,y+8,4,text);
y=y+24;
setcolor(9);
disp_hz16(" zhí wù shí wù měi dài shēng chéng gè shù ",16,y,15);
sprintf(text,"%d",newfoods);
g_text(200,y+8,4,text);
y=y+24;
setcolor(9);
disp_hz16(" biàn yì gàilǜ ",16,y,15);
i=(int)(mutation*100.0);
sprintf(text,"%d",i);
g_text(152,y+8,4,text);
g_draw_frame(0,170,320,399,7,0,8,15," zuì jiā jī yīn xíng ");
x=16;y=194;
setcolor(9);
disp_hz16("sp: wù zhǒng hào ........",x,y,15);y=y+16;
disp_hz16("sl: shòu mìng ..........",x,y,15);y=y+16;
disp_hz16("vf: shì yě ..........",x,y,15);y=y+16;
disp_hz16("tm: jī běn yí dòng mó shì ..",x,y,15);y=y+16;
disp_hz16("cm: yí dòng tè diǎn ......",x,y,15);y=y+16;
disp_hz16("lm: yí dòng néng hào ......",x,y,15);y=y+16;
disp_hz16("ca: xíng dòng tè diǎn ......",x,y,15);y=y+16;
disp_hz16("cr: shàn biàn xìng ........",x,y,15);y=y+16;
disp_hz16("sa: gōng jī sù dù ......",x,y,15);y=y+16;
disp_hz16("da: fáng yù néng lì ......",x,y,15);y=y+16;
disp_hz16("la: gōng jī néng hào ......",x,y,15);y=y+16;
disp_hz16("ef: shí wù xī qǔ xiàolǜ ..",x,y,15);y=y+16;
g_draw_frame(320,16,639,207,7,0,8,15," xū nǐ shì jiè ");
g_draw_frame(320,207,639,399,7,0,8,15," shì dài gè tǐ shù mù biàn huà ");
}
voidg_init_graph()
/* gè tǐ shù jìn huà tú chū shǐ huà */
{
g_rectangle(gx,gy,gx+gxr,gy+gyr,0,1);
g_rectangle(gx,gy,gx+gxr,gy+gyr,6,0);
setcolor(1);
disp_hz16(" shēng wù 1",gx+5,gy-18,15);
g_line(gx+90,gy-10,gx+110,gy-10,1);
setcolor(4);
disp_hz16(" shēng wù 2",gx+120,gy-18,15);
g_line(gx+205,gy-10,gx+225,gy-10,4);
setcolor(0);
disp_hz16(" shì dài shù ",gx+168,gy+gyr+10,15);
g_text(gx-25,gy,0,"100");
g_text(gx-14,gy+gyr,0,"0");
}
voidg_plot_population(gen_num,n1,n2,n1old,n2old)
intgen_num,n1,n2,n1old,n2old;
{
intx,y,gx,gy,x_old,y_old;
chartext;
if(gen_num%10==0)
{
x=gx+(gen_num-1)*gstep;
g_line(x,gy+1,x,gy+gyr-1,1);
sprintf(text,"%d",gen_num);
if(gen_num<100||gen_num%20==0)
g_text(x-8,gy+gyr+5,15,text);
}
x_old=gx+(gen_num-1)*gstep;
x=x_old+gstep;
y_old=gy+gyr-n1old;
y=gy+gyr-n1;
g_line(x_old,y_old,x,y,1);
y_old=gy+gyr-n2old;
y=gy+gyr-n2;
g_line(x_old,y_old,x,y,4);
}
voidg_disp_genotype()/* xiǎn shì zuì jiā gè tǐ de yí chuán jī yīn xíng */
{
inti,j,n0,n1,x,y;
unsignedcharg[g_length];
unsignedcharbits=
{{0,0},{1,4},{5,6},{7,8},{9,11},{12,12},{13,15},
{16,18},{19,21},{22,24},{25,27},{28,31}};
/* huà miàn xiāo chú */
g_rectangle(200,187,319,398,7,1);
if(pop_size!=0)
{
/* huò qǔ gè yí chuán yīn zǐ */
for(i=0;i<g_length;i++)
{
n0=0;n1=0;
for(j=0;j<pop_size;j++)
if(gene[j][i]==0)n0++;
elsen1++;
if(n0>=n1)g[i]=0;elseg[i]=1;
}
x=220;
for(i=0;i<12;i++)
{
y=202+i*16;
for(j=bits[i][0];j<=bits[i];j++)
if(g[j]==0)
g_text(x+(j-bits[i][0])*16,y,4,"0");
else
g_text(x+(j-bits[i][0])*16,y,4,"1");
}
}
}
voidg_disp_char(x,y,x1,y1,x2,y2,v)
intx,y,x1,y1,x2,y2;
unsignedcharv;
{
charc;
if(x>=x1&&x<=x2-8&&y>=y1&&y<=y2-10)
{
switch(v)
{
case0:strcpy(c,"0 ");break;
case1:strcpy(c,"+ ");break;
case2:strcpy(c,"- ");break;
case3:strcpy(c,"x ");
}
g_text(x,y,15,c);
}
}
voidremove_life(n)/* xiāo chú dì n gè gè tǐ */
intn;
{
iflg[n]=0;
world[iatr[n][0]][iatr[n]]=0;
g_disp_unit(iatr[n][0],iatr[n],0);
if(food_size+1<=max_food)
{
food_size++;
fatr[food_size-1][0]=iatr[n][0];
fatr[food_size-1]=iatr[n];
fatr[food_size-1]=1;
fatr[food_size-1]=0;
fflg[food_size-1]=1;
world[iatr[n][0]][iatr[n]]=5;
g_disp_unit(iatr[n][0],iatr[n],5);
}
}
voidremove_food(n)/* xiāo chú dì n gè shí wù */
intn;
{
fflg[n]=0;
world[fatr[n][0]][fatr[n]]=0;
g_disp_unit(fatr[n][0],fatr[n],0);
}
voidmake_lives_and_foods()/* shè zhì xū nǐ huán jìng zhōng shēng wù yǔ shí wù */
{
intx,y,i,j;
pop_size=0;
food_size=0;
for(y=0;y<wy;y++)
for(x=0;x<wx;x++)
{
if(world[x][y]==1||world[x][y]==2)
{
if(pop_size+1<=max_pop)
{
pop_size++;
/* shēng chéng yí chuán yīn zǐ */
gene[pop_size-1][0]=world[x][y]-1;
for(i=1;i<g_length;i++)
gene[pop_size-1][i]=random(2);
/* shè dìng shǔ xìng */
iatr[pop_size-1][0]=x;
iatr[pop_size-1]=y;
iatr[pop_size-1]=70+random(30);
iatr[pop_size-1]=random(sl_min);
}
}
if(world[x][y]==3||world[x][y]==5)
{
if(food_size+1<=max_food)
{
food_size++;
/* shè dìng shǔ xìng */
fatr[food_size-1][0]=x;
fatr[food_size-1]=y;
if(world[x][y]==3)
fatr[food_size-1]=0;
else
fatr[food_size-1]=1;
fatr[food_size-1]=random(tl1-1)+1;
}
}
}
}
voidfind_empty(x,y)/* xún zhǎo xū nǐ huán jìng zhōng de kōng chù， fǎn huí zuò biāo */
int*x,*y;
{
intok;
ok=0;
while(ok==0)
{
*x=random(wx);*y=random(wy);
if(world[*x][*y]==0)ok=1;
}
}
voidmake_world()/* suí jī shè dìng rén gōng huán jìng */
{
inti,j,k,num,x,y;
intok,overlap;
charchoice;
doublesize;
wx=0;
while(wx<10||wx>max_wx)
{
setcolor(15);
disp_hz16(" xū nǐ huán jìng cháng dù (10-60)",10,210,20);
gscanf(300,210,4,0,3,"%s",choice);
wx=atoi(choice);
}
wy=0;
while(wy<10||wy>max_wy)
{
setcolor(15);
disp_hz16(" xū nǐ huán jìng kuān dù (10-32)",10,240,20);
gscanf(300,240,4,0,3,"%s",choice);
wy=atoi(choice);
}
for(i=0;i<wy;i++)
for(j=0;j<wx;j++)
if(i==0||i==wy-1||j==0||j==wx-1)
world[j][i]=4;
elseworld[j][i]=0;
/* shè dìng zhàng 'ài wù */
size=(double)(wx*wy);
num=(int)(size/40.0);
if(num>max_pop)num=max_pop;
for(i=0;i<num;i++)
{
find_empty(&x,&y);
world[x][y]=4;
}
num=(int)(size/5.0);
if(num>max_food)num=max_food;
for(i=0;i<num;i++)
{
ok=0;
while(ok==0)
{
x=random(wx);y=random(wy);
if((world[x][y]!=4)&&
(world[x][y-1]==4||world[x][y+1]==4||
world[x-1][y]==4||world[x+1][y]==4))
{world[x][y]=4;
ok=1;
}
}
}
for(y=0;y<wy;y++)
for(x=0;x<wx;x++)
if(world[x][y]==0)
{
num=0;
for(i=-1;i<=1;i++)
for(j=-1;j<=1;j++)
if(get_world(x+j,y+i)==4)
num++;
if(num>=6)world[x][y]=4;
}
/* shè dìng shēng wù */
num=(int)(size*r_life);
for(i=0;i<num;i++)
{find_empty(&x,&y);
world[x][y]=random(2)+1;
}
/* shè dìng shí wù */
num=(int)(size*r_food);
for(i=0;i<num;i++)
{
find_empty(&x,&y);
world[x][y]=3;
}
}
voidload_world_file()/* dú qǔ xū nǐ huán jìng shù jù wén jiàn shè dìng */
{
file*fopen(),*fpt;
charst[100],c;
inti,j;
if((fpt=fopen("gaworld","r"))==null)exit(-1);
else
{
fscanf(fpt,"%d",&wx);
fscanf(fpt,"%d",&wy);
for(i=0;i<wy;i++)
for(j=0;j<wx;j++)
fscanf(fpt,"%d",&world[j][i]);
fclose(fpt);
}
}
intget_world(x,y)/* zuò biāo (x,y) chù huán jìng zhí */
intx,y;
{
if(x>=0&&x<wx&&y>=0&&y<wy)
return(world[x][y]);
else
return(-1);
}
intdecode_gene(n,sb,bw)/* dì n gè gè tǐ jī yīn xíng jiě mǎ */
intn,sb,bw;/*sb kāi shǐ wèi bw wèi cháng */
{
inti,sum;
sum=0;
for(i=sb;i<sb+bw;i++)
sum=sum*2+gene[n][i];
return(sum);
}
voidmove_pos(n,x1,y1,x2,y2)/* gè tǐ n cóng (x1,y1) yí dòng dào (x2,y2)*/
intn,x1,y1,x2,y2;
{
intsp,loss;
loss=decode_gene(n,12,1)+1;/* yí dòng xiāo hào */
iatr[n]=iatr[n]-loss;/* nèi bù néng liàng gēngxīn */
if(iatr[n]<=0)remove_life(n);
else
{
/* gè tǐ shǔ xìng gēngxīn */
iatr[n][0]=x2;iatr[n]=y2;/*x,y zuò biāo gēngxīn */
/* xiǎn shì gēngxīn */
sp=gene[n][0]+1;
g_disp_unit(x1,y1,0);/* dāng qián wèi zhì (x,y) tú xíng xiāo chú */
world[x1][y1]=0;
g_disp_unit(x2,y2,sp);/* xīn wèi zhì tú xíng biǎo shì */
world[x2][y2]=sp;
}
}
voidmove_randomly(n)/* gè tǐ n 'àn zhào yí dòng mó shì suí jī yí dòng */
intn;
{
/* jī běn yí dòng mó shì 1*/
intpat1={{1,0},{1,1},{0,1},{-1,1},
{-1,0},{-1,-1},{0,-1},{1,-1}};
/* jī běn yí dòng mó shì 2 yǔ 3*/
intpat2_3={{{1,0},{0,1},{-1,0},{0,-1}},
{{1,1},{-1,1},{-1,-1},{1,-1}}};
intpat,x1,y1,x2,y2,rndnum;
pat=decode_gene(n,7,2);
/*pat(0,1,2,3): biǎo shì jī běn yí dòng mó shì */
x1=iatr[n][0];/* dāng qián x zuò biāo */
y1=iatr[n];/* dāng qián y zuò biāo */
if(pat<=1)/* jī běn yí dòng mó shì 1*/
{
rndnum=random(8);
x2=x1+pat1[rndnum][0];/* yí dòng mùdì diǎn x zuò biāo */
y2=y1+pat1[rndnum];/* yí dòng mùdì diǎn y zuò biāo */
}
else/* jī běn yí dòng mó shì 2 yǔ 3*/
{
rndnum=random(4);
x2=x1+pat2_3[pat-2][rndnum][0];
y2=y1+pat2_3[pat-2][rndnum];
}
if(x2>=0&&x2<wx&&y2>=0&&y2<wy)
if(get_world(x2,y2)==0)
move_pos(n,x1,y1,x2,y2);
/* fēi fǎ mùdì diǎn de chǎng hé bù zuò yí dòng */
}
voidmove_individual(n)/* gè tǐ n yí dòng */
intn;
{
intcx,cy,dx,dy,sp,vf,sumx,sumy;
inti,j,a,sgn,num;
doublevect={{1,0},{1,1},{0,1},{-1,1},
{-1,0},{-1,-1},{0,-1},{1,-1}};
doublevx,vy,d1,d2;
double_cos,cos_max;
cx=iatr[n][0];/* dāng qián x zuò biāo */
cy=iatr[n];& | yí chuán suàn fǎ de yùn suàn guò chéng | xuǎn zé ( fù zhì )：
gēn jù gè gè gè tǐ de shì yìng dù， àn zhào yī dìng de guī zé huò fāng fǎ， cóng dì t dài qún tǐ P(t) zhòngxuǎn zé chū yī xiē yōu liáng de gè tǐ yí chuán dào xià yī dài qún tǐ P(t+1) zhōng；
jiāo chā：
jiāng qún tǐ P(t) nèi de gè gè gè tǐ suí jī dā pèi chéng duì， duì měi yī duì gè tǐ， yǐ mǒu gè gàilǜ ( chēng wéi jiāo chā gàilǜ） jiāo huàn tā men zhī jiān de bù fēn rǎn sè tǐ；
biàn yì：
duì qún tǐ P(t) zhōng de měi yī gè gè tǐ， yǐ mǒu yī gàilǜ ( chēng wéi biàn yì gàilǜ ) gǎi biàn mǒu yī gè huò mǒu yī xiē jī yīn zuò shàng de jī yīn zhí wéi qí tā jī yīn zhí。 | | | kē xué | guāng xué | fēn guāng guāng dù fǎ | mó nǐ tuì huǒ suàn fǎ | tuì huǒ suàn fǎ | yí chuán bìng | yí chuán xué | xuè xíng yí chuán | | yí chuán suǒ | liàng zǐ jì suàn | |
| | | liàng zǐ yí chuán suàn fǎ | yí chuán suàn fǎ dìng yì | yí chuán suàn fǎ tè diǎn | | yí chuán suàn fǎ shí lì | yí chuán suàn fǎ de yìng yòng | yí chuán suàn fǎ de xiàn zhuàng | | mó nǐ tuì huǒ yí chuán suàn fǎ | jī xiè yōu huà shè jì yí chuán suàn fǎ | yí chuán suàn fǎ de shù xué jī chǔ | | yí chuán suàn fǎ de yī bān suàn fǎ | jiāo hù shì yí chuán suàn fǎ yuán lǐ jí qí yìng yòng | xié tóng jìn huà yí chuán suàn fǎ lǐ lùn jí yìng yòng | |
|
|
|