Population model (evolutionary algorithm)
ઉત્ક્રાંતિ અલ્ગોરિધમ (ઇ. એ.) નું વસ્તી મોડેલ તેની વસ્તીના માળખાકીય ગુણધર્મોનું વર્ણન કરે છે જેમાં તેના સભ્યો વિષય છે. વસ્તી એ એક પુનરાવર્તનમાં ગણવામાં આવતા ઇએના તમામ સૂચિત ઉકેલોનો સમૂહ છે, જેને જૈવિક રોલ મોડેલ અનુસાર વ્યક્તિઓ પણ કહેવામાં આવે છે. વસ્તીના વ્યક્તિઓ પ્રક્રિયાના આનુવંશિક સંચાલકોની મદદથી સંતાન તરીકે વધુ વ્યક્તિઓ પેદા કરી શકે છે. ઇ. એ. માં સૌથી સરળ અને વ્યાપકપણે ઉપયોગમાં લેવાતું વસ્તી મોડેલ વૈશ્વિક અથવા પેન્મિક્ટિક મોડેલ છે, જે બિનસંરચિત વસ્તીને અનુરૂપ છે. તે દરેક વ્યક્તિને ક્રોસઓવર દ્વારા સંતાનના ઉત્પાદન માટે ભાગીદાર તરીકે વસ્તીના અન્ય કોઈપણ વ્યક્તિને પસંદ કરવાની મંજૂરી આપે છે, જ્યાં સુધી વ્યક્તિઓની તંદુરસ્તી નોંધપાત્ર ભૂમિકા ભજવે ત્યાં સુધી પસંદગીની વિગતો અપ્રસ્તુત છે. વૈશ્વિક સાથીની પસંદગીને કારણે, થોડી પેઢીઓ (ઇ. એ. નું પુનરાવર્તન) પછી વસ્તીમાં થોડી વધુ સારી વ્યક્તિઓની આનુવંશિક માહિતી પ્રચલિત થઈ શકે છે, જો કે આ તબક્કામાં કોઈ વધુ સારી અન્ય સંતાન ઉભરી નથી. જો આ રીતે મળતો ઉકેલ ઇચ્છિત મહત્તમ ન હોય, તો તેને અકાળ અભિસરણ કહેવામાં આવે છે. આ અસર પેન્મિક્ટિક વસ્તીમાં વધુ વખત જોઇ શકાય છે. પ્રકૃતિમાં વૈશ્વિક સમાગમ પુલ ભાગ્યે જ જોવા મળે છે. અવકાશી અંતરને કારણે ચોક્કસ અને મર્યાદિત અલગતા પ્રવર્તે છે. પરિણામી સ્થાનિક પડોશીઓ શરૂઆતમાં સ્વતંત્ર રીતે વિકસિત થાય છે અને મ્યુટન્ટ્સ પાસે ઘણી પેઢીઓ સુધી ટકી રહેવાની વધુ તક હોય છે. પરિણામે, જનીન પૂલમાં જીનોટાઇપિક વિવિધતા પેન્મિક્ટિક વસ્તી કરતાં વધુ સમય સુધી સાચવવામાં આવે છે. તેથી અગાઉની વૈશ્વિક વસ્તીને સબસ્ટ્રક્ચર્સ દ્વારા વિભાજિત કરવી સ્પષ્ટ છે. આ હેતુ માટે બે મૂળભૂત નમૂનાઓ રજૂ કરવામાં આવ્યા હતા, ટાપુ નમૂનાઓ, જે વસ્તીના નિશ્ચિત પેટા વસ્તીમાં વિભાજન પર આધારિત છે જે સમયાંતરે વ્યક્તિઓનું આદાનપ્રદાન કરે છે, અને પડોશી નમૂનાઓ, જે વ્યક્તિઓને ઓવરલેપિંગ પડોશીઓ માટે સોંપે છે, જેને સેલ્યુલર આનુવંશિક અથવા ઉત્ક્રાંતિ અલ્ગોરિધમ્સ (સીજીએ અથવા સીઇએ) તરીકે પણ ઓળખવામાં આવે છે. વસ્તીનું સંકળાયેલ વિભાજન પણ પ્રક્રિયાને અનુરૂપ સમાંતર કરવાનું સૂચવે છે. આ કારણોસર, ઇ. એ. ના સમાંતરકરણના સંબંધમાં સાહિત્યમાં વસ્તીના નમૂનાઓના વિષયની પણ વારંવાર ચર્ચા કરવામાં આવે છે. ટાપુના નમૂનાઓ ટાપુના નમૂનામાં, જેને સ્થળાંતર નમૂના અથવા બરછટ દાણાદાર નમૂના પણ કહેવાય છે, ઉત્ક્રાંતિ કડક રીતે વિભાજિત પેટા વસ્તીમાં થાય છે. આને સર્વગ્રાહી રીતે ગોઠવી શકાય છે, પરંતુ તે હોવું જરૂરી નથી. સમયાંતરે વ્યક્તિઓનું આદાનપ્રદાન થાય છે, જેને સ્થળાંતર કહેવામાં આવે છે. વિનિમય વચ્ચેના સમયને યુગ કહેવામાં આવે છે અને તેનો અંત વિવિધ માપદંડો દ્વારા શરૂ થઈ શકે છેઃ દા. ત. આપેલ સમય પછી અથવા પૂર્ણ પેઢીઓની આપેલ સંખ્યા પછી, અથવા સ્થિરતાની ઘટના પછી. સ્થિરતા શોધી શકાય છે, ઉદાહરણ તરીકે, એ હકીકત દ્વારા કે ટાપુ પર આપેલ પેઢીઓથી કોઈ તંદુરસ્તીમાં સુધારો થયો નથી. ટાપુના નમૂનાઓ વિવિધ નવી વ્યૂહરચના પરિમાણો રજૂ કરે છેઃ પેટા વસ્તીની સંખ્યા ટાપુઓ વચ્ચેના પડોશી સંબંધોઃ તેઓ નક્કી કરે છે કે કયા ટાપુઓને પડોશી ગણવામાં આવે છે અને આમ વ્યક્તિઓનું આદાનપ્રદાન કરી શકે છે, એક સરળ એકદિશાત્મક વીંટી (કાળા તીર) નું ચિત્ર જુઓ અને વધારાના દ્વિદિશાત્મક પડોશી સંબંધો (વધારાના લીલા તીર) દ્વારા તેનું વિસ્તરણ યુગની સમાપ્તિ માટેના માપદંડ, સમકાલિક અથવા અસુમેળ સ્થળાંતર દરઃ સ્થળાંતરમાં સામેલ વ્યક્તિઓની સંખ્યા અથવા પ્રમાણ. સ્થળાંતર કરનારાઓની પસંદગીઃ આ માટે ઘણા વિકલ્પો છે. ઇ. જી. શ્રેષ્ઠ વ્યક્તિઓ સૌથી ખરાબ અથવા અવ્યવસ્થિત રીતે પસંદ કરેલી વ્યક્તિઓનું સ્થાન લઈ શકે છે. સ્થળાંતર દરના આધારે, આ એક સમયે એક અથવા વધુ વ્યક્તિઓને અસર કરી શકે છે. આ પરિમાણો સાથે, પસંદગીનું દબાણ નોંધપાત્ર પ્રમાણમાં પ્રભાવિત થઈ શકે છે. ઉદાહરણ તરીકે, તે ટાપુઓના પરસ્પર જોડાણ સાથે વધે છે અને પેટા વસ્તીની સંખ્યા અથવા યુગની લંબાઈ સાથે ઘટે છે. નેબરહુડ મોડેલ્સ અથવા સેલ્યુલર ઇવોલ્યુશનરી એલ્ગોરિધમ્સ નેબરહુડ મોડેલ, જેને ડિફ્યુઝન મોડેલ અથવા ફાઇન ગ્રેઇન્ડ મોડેલ પણ કહેવાય છે, તે વસ્તીના વ્યક્તિઓ વચ્ચેના ટોપોલોજિકલ પડોશી સંબંધને વ્યાખ્યાયિત કરે છે જે તેમના ફેનોટાઇપિક ગુણધર્મોથી સ્વતંત્ર છે. આ મોડેલનો મૂળભૂત વિચાર ઇ. એ. વસ્તીને જોડાયેલ આલેખ તરીકે વ્યાખ્યાયિત વિશેષ માળખું પ્રદાન કરવાનો છે, જેમાં દરેક શિરોબિંદુ એક વ્યક્તિ છે જે તેના નજીકના પડોશીઓ સાથે વાતચીત કરે છે. ખાસ કરીને, વ્યક્તિઓને વૈચારિક રીતે ટોરોઇડલ જાળીમાં ગોઠવવામાં આવે છે, અને તેમને માત્ર નજીકના વ્યક્તિઓ સાથે ફરીથી જોડાવાની મંજૂરી આપવામાં આવે છે. આ એક પ્રકારનો વિસ્તાર તરફ દોરી જાય છે જેને અંતર દ્વારા અલગતા તરીકે ઓળખવામાં આવે છે. વ્યક્તિના સંભવિત સાથીઓના સમૂહને તેના પડોશી અથવા ડેમ કહેવામાં આવે છે. અડીને આવેલી આકૃતિ દર્શાવે છે કે પીળા રંગથી ચિહ્નિત બે વ્યક્તિઓના સહેજ ઓવરલેપિંગ પડોશીઓ બતાવીને, જેના દ્વારા આનુવંશિક માહિતી બે ડેમ વચ્ચે ફેલાઈ શકે છે. તે જાણીતું છે કે આ પ્રકારના અલ્ગોરિધમમાં, સમાન વ્યક્તિઓ સમૂહ બનાવે છે અને વિશિષ્ટ સ્થાન બનાવે છે જે અર્ધ સીમાઓથી સ્વતંત્ર હોય છે અને, ખાસ કરીને, અર્ધ કરતાં મોટું હોઈ શકે છે. નજીકના જૂથો વચ્ચે કોઈ સ્પષ્ટ સરહદ નથી, અને નજીકના સ્થાનોને સ્પર્ધાત્મક લોકો દ્વારા સરળતાથી વસાહત કરી શકાય છે અને કદાચ આ પ્રક્રિયા દરમિયાન ઉકેલની સામગ્રીને મર્જ કરી શકાય છે. સાથે સાથે, દૂરના સ્થાનોને વધુ ધીમેથી અસર થઈ શકે છે. આ પ્રકારની વસ્તી સાથેના ઇ. એ. સેલ્યુલર ઇ. એ. (સી. ઇ. એ.) અથવા સેલ્યુલર આનુવંશિક અલ્ગોરિધમ્સ (સી. જી. એ.) તરીકે પણ જાણીતા છે. વસ્તીના વ્યક્તિઓને ગોઠવવા માટે સામાન્ય રીતે ઉપયોગમાં લેવાતું માળખું 2D ટોરોઇડલ ગ્રીડ છે, જો કે પરિમાણોની સંખ્યા સરળતાથી વિસ્તૃત કરી શકાય છે (3D સુધી) અથવા ઘટાડી શકાય છે (1D સુધી, દા. ત. એક વીંટી, જમણી બાજુની આકૃતિ જુઓ). ગ્રીડમાં કોઈ ચોક્કસ વ્યક્તિના પડોશને વસ્તીમાં અન્ય લોકોથી મેનહટન અંતરની દ્રષ્ટિએ વ્યાખ્યાયિત કરવામાં આવે છે. મૂળભૂત અલ્ગોરિધમમાં, તમામ પડોશીઓ સમાન કદ અને સમાન આકાર ધરાવે છે. બે ડાયમેન્શનલ સીઇએ માટે બે સૌથી વધુ ઉપયોગમાં લેવાતા પડોશીઓ એલ 5 અને સી 9 છે, ડાબી બાજુની આકૃતિ જુઓ. અહીં L નો અર્થ લીનિયર થાય છે જ્યારે C નો અર્થ કોમ્પેક્ટ થાય છે. દરેક ડેમ એક પેન્મિક્ટિક પેટા વસ્તીનું પ્રતિનિધિત્વ કરે છે જેમાં માતાપિતાને બદલીને સાથીની પસંદગી અને સંતાનની સ્વીકૃતિ થાય છે. સંતાનની સ્વીકૃતિ માટેના નિયમો સ્થાનિક પ્રકૃતિના છે અને પડોશી પર આધારિત છેઃ ઉદાહરણ તરીકે, તે સ્પષ્ટ કરી શકાય છે કે શ્રેષ્ઠ સંતાન માતાપિતાને બદલવા કરતાં વધુ સારું હોવું જોઈએ અથવા, ઓછા કડક રીતે, માત્ર સૌથી ખરાબ વ્યક્તિ કરતાં વધુ સારું હોવું જોઈએ. પ્રથમ નિયમ અભિજાત્યપણુ છે અને બીજા બિન-અભિજાત્યપણુ નિયમ કરતાં વધુ પસંદગીયુક્ત દબાણ ઊભું કરે છે. અભિજાત્ય વર્ગના ઇ. એ. માં, વસ્તીનો શ્રેષ્ઠ વ્યક્તિ હંમેશા ટકી રહે છે. આ સંદર્ભમાં, તેઓ જૈવિક નમૂનાથી વિચલિત થાય છે. પડોશની ઓવરલેપ મોટાભાગે પડોશની સરહદોમાં આનુવંશિક માહિતીના ધીમા ફેલાવાનું કારણ બને છે, તેથી તેનું નામ પ્રસરણ મોડેલ છે. વધુ સારા સંતાનને હવે વસ્તીમાં ફેલાવા માટે પેનમિક્સી કરતાં વધુ પેઢીઓની જરૂર છે. આ સ્થાનિક સ્થાનોના ઉદભવ અને તેમના સ્થાનિક ઉત્ક્રાંતિને પ્રોત્સાહન આપે છે, આમ લાંબા સમય સુધી જીનોટાઇપિક વિવિધતાને જાળવી રાખે છે. પરિણામ એ છે કે દોડ દરમિયાન શોધ જગ્યાને અનુરૂપ પહોળાઈ અને ઊંડાઈ શોધ વચ્ચે વધુ સારું અને ગતિશીલ સંતુલન છે. ઊંડાણપૂર્વકની શોધ વિશિષ્ટ સીમાઓમાં વિશિષ્ટ સ્થળો અને પહોળાઈની શોધમાં અને સમગ્ર વસ્તીના વિવિધ વિશિષ્ટ સ્થળોની ઉત્ક્રાંતિ દ્વારા થાય છે. સમાન પડોશના કદ માટે, આનુવંશિક માહિતીનો ફેલાવો L9 જેવી લંબચોરસ આકૃતિઓ માટે C9 જેવા બ્લોક કરતાં મોટો હોય છે, અને ફરીથી રિંગ કરતાં નોંધપાત્ર રીતે મોટો હોય છે. આનો અર્થ એ છે કે રિંગ પડોશીઓ ઉચ્ચ ગુણવત્તાના પરિણામો પ્રાપ્ત કરવા માટે સારી રીતે અનુકૂળ છે, પછી ભલે તે તુલનાત્મક રીતે લાંબા ગાળાની જરૂર હોય. બીજી બાજુ, જો કોઈને મુખ્યત્વે ઝડપી અને સારા, પરંતુ સંભવતઃ ઓછા શ્રેષ્ઠ પરિણામોમાં રસ હોય, તો 2D ટોપોલોજી વધુ યોગ્ય છે. સરખામણી આનુવંશિક અલ્ગોરિધમ્સ, ઉત્ક્રાંતિ વ્યૂહરચના અને અન્ય ઇ. એ. માં વસ્તીના બંને નમૂનાઓને લાગુ કરતી વખતે, કુલ વસ્તીનું પેટા વસ્તીમાં વિભાજન સામાન્ય રીતે અકાળ અભિસરણનું જોખમ ઘટાડે છે અને એકંદરે વધુ વિશ્વસનીય અને ઝડપી પરિણામો તરફ દોરી જાય છે. પડોશી મોડેલોની સરખામણીમાં ટાપુ મોડેલોને ગેરલાભ છે કારણ કે તેઓ મોટી સંખ્યામાં નવા વ્યૂહરચના પરિમાણો રજૂ કરે છે. સાહિત્યમાં આ વિષય પર પ્રવર્તમાન અભ્યાસો હોવા છતાં, વપરાશકર્તા માટે પ્રતિકૂળ સેટિંગનું ચોક્કસ જોખમ રહે છે. બીજી બાજુ, પડોશી મોડેલો સાથે, માત્ર પડોશીનું કદ નિર્દિષ્ટ કરવું પડે છે અને દ્વિ-પરિમાણીય મોડેલના કિસ્સામાં, પડોશી આકૃતિની પસંદગી ઉમેરવામાં આવે છે. સમાંતરતા કારણ કે બંને વસ્તીના નમૂનાઓ વસ્તીના વિભાજનને સૂચવે છે, તેથી તેઓ ઇ. એ. ને સમાંતર બનાવવા માટેના આધાર તરીકે સારી રીતે અનુકૂળ છે. આ સેલ્યુલર ઇ. એ. ને વધુ લાગુ પડે છે, કારણ કે તેઓ માત્ર તેમના સંબંધિત સભ્યો વિશે સ્થાનિક રીતે ઉપલબ્ધ માહિતી પર આધાર રાખે છે. આમ, આત્યંતિક કિસ્સામાં, દરેક વ્યક્તિને એક સ્વતંત્ર એક્ઝેક્યુશન થ્રેડ સોંપવામાં આવી શકે છે, જેથી સમગ્ર સીઇએ સમાંતર હાર્ડવેર પ્લેટફોર્મ પર ચાલી શકે. ટાપુ મોડેલ સમાંતરકરણને પણ ટેકો આપે છે, દા. ત. દરેક ટાપુને પ્રોસેસર સોંપીને. જો ટાપુઓની પેટા વસ્તીને સર્વગ્રાહી રીતે ગોઠવવામાં આવે, તો પેઢીના વંશજોના તમામ મૂલ્યાંકનને વધુમાં સમાંતર કરી શકાય છે. વાસ્તવિક દુનિયાની એપ્લિકેશનોમાં મૂલ્યાંકન સામાન્ય રીતે સૌથી વધુ સમય લેતો ભાગ હોય છે. અલબત્ત, ટાપુની પેટા-વસ્તીને સી. ઈ. એ. તરીકે ડિઝાઇન કરવી પણ શક્ય છે, જેથી સી. ઈ. એ. ને સમાંતર બનાવવા વિશે અગાઉ કરવામાં આવેલા નિવેદનો લાગુ પડે. આ રીતે, યોગ્ય સમાંતરતા સાથે અધિક્રમિક વસ્તી માળખાં બનાવી શકાય છે. માત્ર તુલનાત્મક રીતે મોંઘા કોમ્પ્યુટર ક્લસ્ટર્સ જ નહીં પરંતુ સસ્તા ગ્રાફિક્સ કાર્ડ્સ (જી. પી. યુ.) નો પણ સમાંતરતા માટે ઉપયોગ કરી શકાય છે. જો કે, એ વાત પર ભાર મૂકવો મહત્વપૂર્ણ છે કે સીઇએ, અથવા ટાપુઓમાં વહેંચાયેલી વસ્તી સાથેના ઇએ, એક શોધ મોડેલનું પ્રતિનિધિત્વ કરે છે જે પરંપરાગત ઇએથી ઘણી રીતે અલગ છે. વધુમાં, તેઓ ક્રમિક અને સમાંતર બંને પ્લેટફોર્મ પર ચાલી શકે છે, જે એ હકીકતને પ્રકાશિત કરે છે કે મોડેલ અને અમલીકરણ બે અલગ અલગ વિભાવનાઓ છે. ગ્રંથસૂચિ એરિક કેન્ટુ-પાઝ (2001): કાર્યક્ષમ અને સચોટ સમાંતર આનુવંશિક અલ્ગોરિધમ્સ (પીએચડી થીસીસ, યુનિવર્સિટી ઓફ ઇલિનોઇસ, અર્બાના-શેમ્પેન, યુએસએ). સ્પ્રિંગર, ન્યૂયોર્ક, એનવાય. માર્ટિના ગોર્જ્સ-શ્લેયટર (1990): આનુવંશિક અલ્ગોરિધમ્સ અને વસ્તી માળખાં-એક વ્યાપક સમાંતર અલ્ગોરિધમ. પીએચડી થીસીસ, યુનિવર્સિટી ડોર્ટમંડ, ફેકલ્ટી ફોર ઇન્ફોર્મેટિક, જર્મની. એનરિક આલ્બા, બેર્નાબે ડોર્રોન્સોરો (2008): સેલ્યુલર આનુવંશિક અલ્ગોરિધમ્સ. સ્પ્રિંગર, ન્યૂયોર્ક, એનવાય. ડર્ક સુધોલ્ટ (2015): સમાંતર ઉત્ક્રાંતિ અલ્ગોરિધમ્સ. જાનુઝ કેક્પ્રઝીકમાં, વિટોલ્ડ પેડ્રીઝ (આવૃત્તિઓ. ): સમાંતર ઉત્ક્રાંતિ અલ્ગોરિધમ્સ. સ્પ્રિંગર, બર્લિન, હીડલબર્ગ, પીપી. 929-959 ગેબ્રિએલ લુકે, એનરિક આલ્બા (2011): સમાંતર આનુવંશિક અલ્ગોરિધમ્સ. સ્પ્રિંગર, બર્લિન હીડલબર્ગ. સેલ્યુલર ઓટોમેટન ડ્યુઅલ-ફેઝ ઇવોલ્યુશન ઇવોલ્યુશનરી અલ્ગોરિધમ મેટાહેરિસ્ટિક રેફરન્સ ઇવોલ્યુશનરી અલ્ગોરિધમ્સ પણ જુઓ.