Crossover (genetic algorithm)
આનુવંશિક અલ્ગોરિધમ્સ અને ઉત્ક્રાંતિ ગણતરીમાં, ક્રોસઓવર, જેને પુનઃસંયોજન પણ કહેવાય છે, તે આનુવંશિક સંચાલક છે જેનો ઉપયોગ નવા સંતાન પેદા કરવા માટે બે માતાપિતાની આનુવંશિક માહિતીને જોડવા માટે થાય છે. તે હાલની વસ્તીમાંથી અચોક્કસ રીતે નવા ઉકેલો પેદા કરવાની એક રીત છે, અને તે જીવવિજ્ઞાનમાં જાતીય પ્રજનન દરમિયાન થતા ક્રોસઓવર જેવું જ છે. ઉકેલો હાલના ઉકેલની ક્લોનિંગ દ્વારા પણ પેદા કરી શકાય છે, જે અલૈંગિક પ્રજનન જેવું જ છે. નવા ઉત્પન્ન થયેલા ઉકેલોને વસ્તીમાં ઉમેરતા પહેલા પરિવર્તિત કરી શકાય છે. ઉત્ક્રાંતિ ગણતરીમાં વિવિધ અલ્ગોરિધમ્સ આનુવંશિક માહિતીને સંગ્રહિત કરવા માટે વિવિધ ડેટા સ્ટ્રક્ચરનો ઉપયોગ કરી શકે છે, અને દરેક આનુવંશિક રજૂઆતને વિવિધ ક્રોસઓવર ઓપરેટરો સાથે ફરીથી જોડી શકાય છે. સામાન્ય માહિતી માળખાં કે જેને ક્રોસઓવર સાથે ફરીથી જોડી શકાય છે તે બીટ એરે, વાસ્તવિક સંખ્યાઓના વેક્ટર અથવા વૃક્ષો છે. નીચે પ્રસ્તુત ઓપરેટરોની સૂચિ કોઈ પણ રીતે સંપૂર્ણ નથી અને મુખ્યત્વે આ ડાયડિક આનુવંશિક ઓપરેટર પ્રકારનાં અનુકરણીય ઉદાહરણ તરીકે કામ કરે છે. વધુ સંચાલકો અને વધુ વિગતો સાહિત્યમાં મળી શકે છે. દ્વિસંગી એરે માટે ક્રોસઓવર પરંપરાગત આનુવંશિક અલ્ગોરિધમ્સ આનુવંશિક માહિતીને બીટ એરે દ્વારા રજૂ કરાયેલા રંગસૂત્રમાં સંગ્રહિત કરે છે. બીટ એરે માટે ક્રોસઓવર પદ્ધતિઓ લોકપ્રિય છે અને આનુવંશિક પુનઃસંયોજનનું દૃષ્ટાંતરૂપ ઉદાહરણ છે. એક-બિંદુ ક્રોસઓવર બંને માતાપિતાના રંગસૂત્રો પરનો એક બિંદુ અવ્યવસ્થિત રીતે પસંદ કરવામાં આવે છે, અને તેને 'ક્રોસઓવર બિંદુ' તરીકે નિયુક્ત કરવામાં આવે છે. તે બિંદુની જમણી બાજુના બિટ્સ બે પિતૃ રંગસૂત્રો વચ્ચે અદલાબદલી કરવામાં આવે છે. આ બે સંતાનમાં પરિણમે છે, દરેક બંને માતાપિતા પાસેથી કેટલીક આનુવંશિક માહિતી ધરાવે છે. બે-બિંદુ અને કે-બિંદુ ક્રોસઓવર બે-બિંદુ ક્રોસઓવરમાં, બે ક્રોસઓવર બિંદુઓ પિતૃ રંગસૂત્રોમાંથી અવ્યવસ્થિત રીતે પસંદ કરવામાં આવે છે. બે બિંદુઓ વચ્ચેના બિટ્સને મૂળ સજીવો વચ્ચે અદલાબદલી કરવામાં આવે છે. બે-પોઇન્ટ ક્રોસઓવર એ વિવિધ ક્રોસઓવર પોઇન્ટ સાથે બે સિંગલ-પોઇન્ટ ક્રોસઓવર કરવા સમાન છે. આ વ્યૂહરચનાને કોઈપણ હકારાત્મક પૂર્ણાંક k માટે k-પોઇન્ટ ક્રોસઓવરમાં સામાન્યીકૃત કરી શકાય છે, જેમાં k ક્રોસઓવર પોઇન્ટ પસંદ કરી શકાય છે. યુનિફોર્મ ક્રોસઓવર યુનિફોર્મ ક્રોસઓવરમાં, સામાન્ય રીતે, દરેક બીટ સમાન સંભાવના સાથે પેરેન્ટમાંથી પસંદ કરવામાં આવે છે. અન્ય મિશ્રણ ગુણોત્તરનો કેટલીકવાર ઉપયોગ કરવામાં આવે છે, જેના પરિણામે સંતાન એક પિતૃ પાસેથી બીજા કરતાં વધુ આનુવંશિક માહિતી મેળવે છે. એકસમાન ક્રોસઓવરમાં, આપણે રંગસૂત્રને વિભાગોમાં વહેંચતા નથી, તેના બદલે આપણે દરેક જનીનની અલગ રીતે સારવાર કરીએ છીએ. આમાં, આપણે અનિવાર્યપણે દરેક રંગસૂત્ર માટે એક સિક્કો ફેરવીએ છીએ તે નક્કી કરવા માટે કે તે ઓફ-સ્પ્રિંગમાં શામેલ થશે કે નહીં. પૂર્ણાંક અથવા વાસ્તવિક મૂલ્યના જીનોમ માટે ક્રોસઓવર ઉપર પ્રસ્તુત ક્રોસઓવર ઓપરેટરો માટે અને બીટ સ્ટ્રિંગ્સ માટે મોટાભાગના અન્ય ક્રોસઓવર ઓપરેટરો માટે, તે માને છે કે તેઓ પૂર્ણાંક અથવા વાસ્તવિક મૂલ્યના જીનોમ અનુસાર પણ લાગુ કરી શકાય છે, જેમના જનીનોમાં દરેક પૂર્ણાંક અથવા વાસ્તવિક મૂલ્યની સંખ્યા ધરાવે છે. વ્યક્તિગત બિટ્સને બદલે, પૂર્ણાંક અથવા વાસ્તવિક-મૂલ્યવાન સંખ્યાઓ પછી ફક્ત બાળ જીનોમમાં નકલ કરવામાં આવે છે. સંતાન બે માતાપિતા દ્વારા ફેલાયેલા હાયપરબોડીના બાકીના ખૂણાઓ પર આવેલું છે અને ત્રિ-પરિમાણીય કેસ માટે સાથેની છબીમાં તેનું ઉદાહરણ છે. ડિસ્ક્રીટ રિકોમ્બિનેશન જો બીટ સ્ટ્રિંગ્સ માટે યુનિફોર્મ ક્રોસઓવરના નિયમો સંતાનની પેઢી દરમિયાન લાગુ કરવામાં આવે, તો તેને ડિસ્ક્રીટ રિકોમ્બિનેશન પણ કહેવામાં આવે છે. મધ્યવર્તી પુનઃસંયોજન આ પુનઃસંયોજન સંચાલકમાં, બાળ જીનોમના એલીલ મૂલ્યો બે પેરેન્ટ જીનોમના એલીલને મિશ્રિત કરીને ઉત્પન્ન થાય છે અનેઃ જનીન દીઠ અવ્યવસ્થિત રીતે સમાન રીતે વહેંચાય છે અંતરાલની પસંદગીનું કારણ એ છે કે પેરેન્ટ જનીનોના એલીલ મૂલ્યો દ્વારા ફેલાયેલા હાયપરબોડીના આંતરિક ભાગ ઉપરાંત વધુમાં સંતાનના મૂલ્યોની શ્રેણી માટે ચોક્કસ વાતાવરણ પ્રશ્નમાં છે. એલીલ મૂલ્યોને ઘટાડવાની વૃત્તિને પ્રતિકાર કરવા માટે એક મૂલ્યની ભલામણ કરવામાં આવે છે જે અન્યથા અહીં અસ્તિત્વમાં છે. અડીને આવેલી આકૃતિ દ્વિ-પરિમાણીય કેસ માટે બે અનુકરણીય પેરેન્ટ્સના સંભવિત નવા એલીલ્સની શ્રેણી અને મધ્યવર્તી પુનઃસંયોજન દર્શાવે છે. અલગ પુનઃસંયોજનના સંતાનો પણ રચાયેલા છે. મધ્યવર્તી પુનઃસંયોજન વર્ચ્યુઅલ મૂળાક્ષર સિદ્ધાંત દ્વારા જરૂરી બાળ જીનોમના એલીલ મૂલ્યોની અંકગણિત ગણતરીને સંતોષે છે. અલગ અને મધ્યવર્તી પુનઃસંયોજનનો ઉપયોગ ઉત્ક્રાંતિ વ્યૂહરચનામાં પ્રમાણભૂત તરીકે થાય છે. ક્રમચયો માટે ક્રોસઓવર સંયોજન કાર્યો માટે, ક્રમચયો સામાન્ય રીતે ઉપયોગમાં લેવાય છે જે ખાસ કરીને જીનોમ માટે રચાયેલ હોય છે જે પોતે સમૂહના ક્રમચયો હોય છે. અંતર્ગત સમૂહ સામાન્ય રીતે અથવા નો સબસેટ હોય છે. જો આવા જીનોમ માટે પૂર્ણાંક જીનોમ માટે 1-અથવા એન-પોઇન્ટ અથવા યુનિફોર્મ ક્રોસઓવરનો ઉપયોગ કરવામાં આવે, તો બાળ જીનોમમાં કેટલાક મૂલ્યો બે વાર હોઈ શકે છે અને અન્ય ગુમ થઈ શકે છે. આને આનુવંશિક સુધારણા દ્વારા સુધારી શકાય છે, દા. ત. અન્ય બાળ જિનોમમાંથી ગુમ થયેલા જનીનો માટે સ્થિતિસ્થાપક વફાદારીમાં બિનજરૂરી જનીનોને બદલીને. અમાન્ય સંતાનની ઉત્પત્તિને ટાળવા માટે, ક્રમચયો માટે વિશેષ ક્રોસઓવર ઓપરેટરો વિકસાવવામાં આવ્યા છે જે ક્રમચયો માટે આવા ઓપરેટરોની મૂળભૂત જરૂરિયાતોને પૂર્ણ કરે છે, એટલે કે પ્રારંભિક ક્રમચયોના તમામ ઘટકો પણ નવા ક્રમમાં હાજર હોય છે અને માત્ર ક્રમ બદલવામાં આવે છે. તેને સંયુક્ત કાર્યો વચ્ચે અલગ કરી શકાય છે, જ્યાં તમામ સિક્વન્સ સ્વીકાર્ય છે, અને જ્યાં અસ્વીકાર્ય આંશિક સિક્વન્સના સ્વરૂપમાં અવરોધો છે. પ્રથમ કાર્ય પ્રકારનો એક જાણીતો પ્રતિનિધિ ટ્રાવેલિંગ સેલ્સમેન પ્રોબ્લેમ (ટી. એસ. પી.) છે, જ્યાં ધ્યેય ટૂંકા પ્રવાસ પર બરાબર એક જ વાર શહેરોના સમૂહની મુલાકાત લેવાનું છે. મર્યાદિત કાર્ય પ્રકારનું ઉદાહરણ બહુવિધ કાર્યપ્રવાહોનું સમયપત્રક છે. વર્કફ્લોમાં કામના કેટલાક વ્યક્તિગત પગલાઓ પર શ્રેણીબદ્ધ અવરોધોનો સમાવેશ થાય છે. ઉદાહરણ તરીકે, વર્કપીસમાં અનુરૂપ છિદ્ર ડ્રિલ કરવામાં ન આવે ત્યાં સુધી દોરી કાપી શકાતી નથી. આવી સમસ્યાઓને ક્રમ આધારિત ક્રમચયો પણ કહેવામાં આવે છે. નીચેનામાં, બે ક્રોસઓવર ઓપરેટરોને ઉદાહરણ તરીકે રજૂ કરવામાં આવ્યા છે, ટી. એસ. પી. દ્વારા પ્રેરિત આંશિક રીતે મેપ કરેલ ક્રોસઓવર (પી. એમ. એક્સ.) અને ઓર્ડર-આધારિત ક્રમચયો માટે રચાયેલ ઓર્ડર ક્રોસઓવર (ઓ. એક્સ. 1). દરેક કિસ્સામાં પિતૃ રંગસૂત્રોની આપ-લે કરીને બીજું સંતાન પેદા કરી શકાય છે. આંશિક રીતે મેપ કરેલ ક્રોસઓવર (પી. એમ. એક્સ.) પી. એમ. એક્સ. ઓપરેટરની રચના સમસ્યાઓ જેવી ટી. એસ. પી. માટે પુનઃસંયોજન ઓપરેટર તરીકે કરવામાં આવી હતી. પ્રક્રિયાની સમજૂતી એક ઉદાહરણ દ્વારા સચિત્ર છેઃ ઓર્ડર ક્રોસઓવર (OX1) ઓર્ડર ક્રોસઓવર તેના મૂળ સ્વરૂપમાં ડેવિસ પર પાછો જાય છે અને અહીં બે કરતા વધુ ક્રોસઓવર પોઇન્ટ સાથે સહેજ સામાન્યીકૃત સંસ્કરણમાં રજૂ કરવામાં આવે છે. તે બીજા પિતૃ પાસેથી સંતાનમાં સંબંધિત ક્રમ વિશેની માહિતી સ્થાનાંતરિત કરે છે. પ્રથમ, ક્રોસઓવર બિંદુઓની સંખ્યા અને સ્થિતિ અવ્યવસ્થિત રીતે નક્કી કરવામાં આવે છે. પરિણામી જનીન સિક્વન્સ પછી નીચે વર્ણવ્યા મુજબ પ્રક્રિયા કરવામાં આવે છેઃ અન્ય બાબતોમાં, ઓર્ડર ક્રોસઓવર બહુવિધ વર્કફ્લો સુનિશ્ચિત કરવા માટે સારી રીતે અનુકૂળ છે, જ્યારે તેનો ઉપયોગ 1-અને એન-પોઇન્ટ ક્રોસઓવર સાથે કરવામાં આવે છે. ક્રમચયો માટે વધુ ક્રોસઓવર ઓપરેટરો સમય જતાં, ક્રમચયો માટે મોટી સંખ્યામાં ક્રોસઓવર ઓપરેટરોની દરખાસ્ત કરવામાં આવી છે, તેથી નીચેની સૂચિ માત્ર એક નાની પસંદગી છે. વધુ માહિતી માટે, વાચકને સાહિત્યનો સંદર્ભ આપવામાં આવે છે. સાઇકલ ક્રોસઓવર (CX) ઓર્ડર-બેઝ્ડ ક્રોસઓવર (OX2) પોઝિશન-બેઝ્ડ ક્રોસઓવર (POS) એજ રિકોમ્બિનેશન વોટિંગ રિકોમ્બિનેશન (VR) અલ્ટરનેટિંગ-પોઝિશન્સ ક્રોસઓવર (AP) મેક્સિમલ પ્રિઝર્વેટિવ ક્રોસઓવર (MPX) મર્જ ક્રોસઓવર (MX) સિક્વેન્શલ કન્સ્ટ્રક્ટિવ ક્રોસઓવર ઓપરેટર (SCX) અગાઉ રજૂ કરાયેલ આનુવંશિક અથવા વધુ સામાન્ય રીતે, ઉત્ક્રાંતિના અલ્ગોરિધમ્સ દ્વારા TSP જેવી સમસ્યાઓનું સમાધાન કરવાનો સામાન્ય અભિગમ, ગેરકાયદેસર વંશજોને સુધારવા અથવા સંચાલકોને યોગ્ય રીતે સમાયોજિત કરવાનો છે જેથી ગેરકાયદેસર સંતાન પ્રથમ સ્થાને ન ઉદ્ભવે. વૈકલ્પિક રીતે, રિયાઝી બેવડા રંગસૂત્ર પ્રતિનિધિત્વનો ઉપયોગ સૂચવે છે, જે ગેરકાયદેસર સંતાનને ટાળે છે. ઇવોલ્યુશનરી અલ્ગોરિધમ આનુવંશિક પ્રતિનિધિત્વ તંદુરસ્તી કાર્ય પસંદગી (આનુવંશિક અલ્ગોરિધમ) ગ્રંથસૂચિ જ્હોન હોલેન્ડ (1975) પણ જુઓ. નેચરલ એન્ડ આર્ટિફિશિયલ સિસ્ટમ્સમાં અનુકૂલન, પીએચડી થીસીસ, યુનિવર્સિટી ઓફ મિશિગન પ્રેસ, એન આર્બર, મિશિગન. . સંદર્ભો બાહ્ય કડીઓ ન્યૂઝગ્રુપઃ comp.ai.genetic FAQ-ક્રોસઓવર પરનો વિભાગ જુઓ (જેને પુનઃસંયોજન તરીકે પણ ઓળખવામાં આવે છે). ઉત્ક્રાંતિ અલ્ગોરિધમ્સ આનુવંશિક અલ્ગોરિધમ્સ