Monday, March 19, 2012

அறிவார்ந்த வடிவமைப்பு அறிவோம் பகுதி 10: வியாபாரியின் [மிக குறைந்த]பயணப்பாதை [Traveling Salesman Problem]



கடந்த இரு பதிவுகளில் பரிணாம செயலாக்க முறை[evolutionary algorithms] என்னும் பரிணாமத்தின் மாதிரி குறித்து கற்று வருகிறோம்.இப்பதிவில் ஒரு சிறிய எடுத்துக்காட்டு மட்டும் பார்த்துவிட்டு பிறகு வில்லியம் டெம்ஸ்கியின் பரிணாம விமர்சனம் குறித்த அவரது ஆய்வுக் கட்டுரைகள் பற்றி விவாதிப்போம்.

பரிணாமம் என்பது இயற்கைச் சூழலுக்கு ஏற்ப இயலும் உயிரினங்களின் தலைமுறை ரீதியான் மாற்றம்  என்பதை நினைவு கூறுதல் நலம்.இயற்கைச் சூழலும் மாறிக் கொண்டே இருப்பதால் ஒரு சூழலில் தாக்குப் பிடித்த உயிரினங்கள் இன்னொரு சூழலில் அழியலாம்.ஆகவே இயற்கை சூழல் மாறுவதை ஒரு மாறும் சூழல் அல்லது இலக்கு அற்ற ப்யணமாக்வே வரையறுக்க இயலும்.பரிணாமத்தில் மனிதன் தோன்றியது ஒரு விபத்தே தவிர மனிதனை படைக்கும் நோக்கில் நடந்தது அல்ல.

இப்பூவுலகின் வளங்கள் அனைத்தும் மனிதர்களுக்கே உரித்தானது என்னும் கொள்கை பரிணாமத்தின் படி தவறு. . பூமியில் மனிதன் இல்லா காலமும்[<99.999%) இருந்ததும் உண்மையாதலால் ,இல்லாமல் போகும் காலமும் வரலாம்.இயற்கையை  மதித்து பாதுகாத்தால் மட்டுமே மனிதன் உள்ளிட்ட பல் உயிரினங்கள் நீடித்து வாழ முடியும் என்பதற்காகவே இதை கூறுகிறோம்..

சரி எடுத்துக்காட்டுக்கு வருவோம்.முதலில் எந்த வகை கணித முடிவெடுக்கும் புதிர்களுக்கு இம்முறை பயன்படுத்த‌ப்பட வேண்டும் என்பதை அறிய வேண்டும்.

1.பல தீர்வுகள் உள்ள புதிராக் இருக்க வேண்டும்.ஒரு தீர்வு என்றல் பிற கணித முறைகளே எளிதாக் தீர்த்து விடும்.

2.தீர்வுகளின் வாய்ய்புகள் மிக அதிகமாக் இருக்க வேண்டும்.குறைவான் தீர்வுகள் உள்ள புதிரை எளிதாக தீர்த்துவிடலாம்.


கணிணியியல்,கணிதம் ஆகியவற்றில் ஒரு முக்கிய புதிரான வியாபாரியின் [மிக குறைந்த]பயணப்பாதை கண்டுபிடிக்கும் புதிரை[Traveling Salesman Problem] எடுத்துக் கொள்வோம்.


இது என்ன?.

ஒரு வியாபாரி பல் ஊர்களுக்கு சென்று வியாபாரம் செய்துவிட்டு பயணம் தொடங்கிய [சொந்த] ஊருக்கே வர வேண்டும்.அப்படி செல்வதற்கு பயணம் எந்த ஊர்களின் வழி சென்றால் தூரம் மிக குறைவாக் இருக்கும் என கண்டறிவதுதான். ஒவ்வொரு ஊருக்கும் ஒருமுறை மட்டுமே செல்ல வேண்டும்,திட்டமிட்ட அனைத்து ஊர்களுக்கும் செல்ல வேண்டும் உடனே தூரம் மட்டும்தான முக்கியம் இதர சில விடயங்களும்[Transport, buying raw material, time management etc..] உண்டே என சிந்திக்கும் நண்பர்களுக்கு,இங்கு நாம் பரிணாம செய்லாக்கத்தின் பயன் பாட்டுக்கு ஒரு எளிய எடுத்துக் காட்டு மட்டுமே கற்கிறோம் என்பதை நினைவு கொள்ள வேண்டுகிறேன். இப்புதிரின் பல வடிவங்களையும் பரிணாம் செயலாக்க முறை கொண்டு தீர்க்க இயலும் என்பதையும் வலியுறுத்துகிறேன்.

சரி இந்த புதிர் எப்படி வரையறுக்கப்படும்.இரு பரிமாண தளத்தில் சில புள்ளிகளின் ஆயத் தொலைகள் கொடுக்கப்ப்டும்.ஒரு புள்ளியில் ஆரம்பித்து அனைத்து புள்ளிகளையும் தொட்டு வந்து தொடங்கிய புள்ளிக்கே வர வேண்டும்.
 

ஒரு N ஊர்கள் கொண்ட புதிருக்கு (n-1])![factorial என்னும் தொடர் பெருக்கல 19* 18*17*....*3*2*1]  பாதைகள் உண்டு(எப்படி? சிந்திக்க மாட்டீர்களா!!!!!!).20 ஊர்கள் கொண்ட புதிருக்கு 19! [=1.2165 x 10^17]வாய்ய்புகள் உண்டு..
மேலே காட்டப்பட்டுள்ல புதிரில் 4 ஊர்கள் உள்ளதால் 3! =3*2*1=6 பாதைகள் மொத்தம் உண்டு.

1.ABCDA=20+30+12+35=97

2.ABDCA=20+34+12+42=108

3. ACBDA=42+30+34+35=141

4. .ACDBA=42+12+34+20=108

5. ADBCA=35+34+30+42=141

6.ADCBA=35+12+30+20=97

இது  ஒத்த தன்மை(symmetry) உள்ள புதிர் என்பதால் வாய்புகள் 0.5*(N-1)!=6/2=3 ஆகும்.ஒத்த தனமை எனில் இரு ஊர்களுக்கு போகும் திரும்பி வரும் பாதைகளின் தூரம் சமம்.இந்த புதிருக்கு இரு விடைகள் அதாவது ஒன்று ,ஆறாம் தீர்வுகள் மிக குறைந்த தூரம் 97 அளிக்கிறது.

ஊர்களின் எண்ணிக்கை அதிகரிக்கும் போது வாய்ய்புகள் பல மடங்கு அதிகரிப்பதால் இப்படி அனைத்து வாய்ய்ப்பு பாதைகளையும் சோதிக்க இயலாது.ஆகவே இதற்கு பரிணாம் செயலாக்க முறை எப்படி பயன் படுத்துவது என அறிவோம்.
 
இது குறித்து அதிகம் எழுதவே விருப்பம் எனினும் இத்தொடர் பதிவில் அ.வ[ID] கொள்கையாக்கம் பற்றி விள்க்குவதே நமது முக்கிய நோக்கமாகும்.ஆகவே நுட்பமாக எப்படி தீர்வு காண்பது என்பதை விட மிகவும் பொதுப்படையாக பரிணாம் செய்லாக்க முறை கொண்டு விள்க்குவதை மேற்கொள்கிரேன்.அதிக விவரம் வேண்டும் நண்பர்கள்களுக்கு பின்னூட்டம் மூலம் சரி செய்கிறேன்.

இப்புதிரை தீர்க்க பரிணாம‌ செய்லாக்க முறை இவ்வாறு செய்லபடுத்தப்படுகிறது.

ஒரு 10 ஊர்கள் கொண்ட புதிரை எடுத்துக் கொள்வோம்.அந்த ஊர்கள் A,B,C,D,E,F,G,H,I,J என குறிக்க்லாம்.

1. தொடக்க தீர்வுகள்[பாதைகள்] சில [எ.கா 20] எடுத்துக் கொள்ளப் படுகிறது.

2.இதில் அதிக தூரம் உள்ள பாதைகள் நீகப்பட்டு அதற்கு  பதிலாக  குறைந்த தூரம் உள்ள பாதைகளின் பிரதிகள் இடப்படுகின்றன்.[Selection]

3. மொத்தம் உள்ள 20 பாதைகள் 10 ஜோடிகள் ஆக கருதப்பட்டு ஜோடிகள் இடையே சில வாய்ப்புள்ள‌ பகுதிகள் இட மாற்றம் செய்யப்படுகின்றன்.[Cross over]
e.g BCDI-----------------IDBC

3. சில பாதைகளில் சிறு மாற்றம் பாதையில் ஏற்படுத்தப்படுகிறது எ.கா  ABC will become ….ACB [Mutation]

4.இபோது புதிதாக் 20 பாதைகள் கிடைத்து உள்ளன.இது ஒரு தலைமுறை இது தொடர்சியாக் நடக்கும் போது தீர்வுகள் கிடைக்கும்.

The genetic algorithm is sequence of following operations that repeated in generations loop:

1) find length of paths

2) find probabilities

3) prepare to crossover according probabilities

4) crossover, parents replaced with children.

5) mutations
இந்த கலப்பு[cross over],சிறுமாற்றம்[mutations] என்பது பல வகைகளில் செய்ய இயலும்.இப்படி தீர்க்கப்படும் ஒரு காணொளி பாருங்கள். 




இது எப்படி மிக எளிதான் செயல்பாடுகளாக் உள்ளதே இக்கடினமான் புதிரை எப்படி தீர்க்கும் எனில் இது என்க்கும் முதலில் வந்த சந்தேகம்தான் ,பிறகு இப்புதிர் உள்ளிட்ட பல் புதிர்களுக்கு மென்பொருள்கள் மூலம் தீர்வு கண்ட பின்பே புரிந்தது.


ஒரு குழு தீர்வுகளை எடுத்து அதில் பரிணாம செயல்முறைகளை[evolutionary operations] தலைமுறை[generations] ரீதியாக பயன்படுத்தினால் தீர்வு[கள்] கிடைக்கிறது, இதற்கு பல மென்பொருள்களும் உண்டு என்பதை மட்டும் புரிந்து கொண்டால் போதும்.

இது குறித்து நிறைய எழுத முடியும் ஏன்றாலும்  இப்பதிவு குறிதத‌ ச‌நந்தேகங்களுக்கு மட்டும் தேவைப்பட்டால் இன்னொரு பதிவு எழுத த்யாராக் உள்ளேன்.

இல்லையெனில் பரிணாம் செய்லாக்க முறை மூலம் பல கடினமான் முடிவெடுக்கும் புதிர்கள் விடை காண இயலும்,இது அதிக பயன்பாடுள்ள கணித முறை, பரிணாம கொள்கையின் மாதிரி என்பதை மனதில் இருத்தினால் போதுமானது.


நன்றி




10 comments:

  1. நண்பர் சுவனப்பிரியனின் எதிர்கால பதிவுகள்.
    1.அப்துல் கலாம் ஜனாதிபதி ஆகி இருக்க கூடாது!!!!
    2.அபுல் கலம் ஆசாத் கல்வி அமைச்சர் ஆனதும் தவறு.
    3.பாகிஸ்தானின் அப்துஸ் சலாமிற்கு நோபல் பரிசு கொடுத்தது தவறு
    4.அசாருத்தீன் கிரிக்கெட் அணித் தலைவர் ஆனது தவறு!.
    5.உமறுப்புலவர் சீறப்புராணம் எழுதியது த்வறு!
    6.கவிக்கோ அப்துல் ரகுமான் கவிதை எழுதுவதும் தவறு!
    ..........

    போட்டுத் தாக்குங்கள்!!!!!!!!!!!!!!!
    ஹா ஹா ஹா
    நன்றி

    ReplyDelete
  2. நண்பர் சார்வாகன்!

    //நண்பர் சுவனப்பிரியனின் எதிர்கால பதிவுகள்.
    1.அப்துல் கலாம் ஜனாதிபதி ஆகி இருக்க கூடாது!!!!
    2.அபுல் கலம் ஆசாத் கல்வி அமைச்சர் ஆனதும் தவறு.
    3.பாகிஸ்தானின் அப்துஸ் சலாமிற்கு நோபல் பரிசு கொடுத்தது தவறு
    4.அசாருத்தீன் கிரிக்கெட் அணித் தலைவர் ஆனது தவறு!.
    5.உமறுப்புலவர் சீறப்புராணம் எழுதியது த்வறு!
    6.கவிக்கோ அப்துல் ரகுமான் கவிதை எழுதுவதும் தவறு!//

    ரஹ்மானுக்கு ஆஸ்கார் கொடுத்ததில் எனக்கு சந்தோஷமே! திறமைமிக்கவரை தேடித்தான் கொடுத்துள்ளார்கள். இஸ்மாயில் தர்பார்தான் பொறாமையால் ரஹ்மானுக்கு ஆஸ்கார் கொடுத்திருக்கக் கூடாது என்கிறார். பதிவை இன்னொர முறை நன்றாக படியுங்கள்.

    //5.உமறுப்புலவர் சீறப்புராணம் எழுதியது த்வறு!//

    கண்டிப்பாக! ஒரு தலைப்பை எடுத்துக் கொடுத்ததற்கு நன்றி! முகமது நபியை பல இடங்களில் இறைவனுக்கு ஒப்ப பாடல் பாடியுள்ளார். நடக்காத சம்பவங்களை எல்லாம் சுவைக்காக அதிகப்படுத்தி எழுதியுள்ளார். இதை எல்லாம் இஸ்லாம் தடுக்கிறது.

    // 6.கவிக்கோ அப்துல் ரகுமான் கவிதை எழுதுவதும் தவறு!//

    உண்மைகளை கவிதைகளாக கவிக்கோ வடிக்கட்டும். இவரும் ஒரு தர்ஹா பிரியர். ஆக... இசை, கவிதை இதில் லயித்தவர்களெல்லாம் தர்ஹா விரும்பிகளாக இருப்பதையும் நாம் பார்க்கிறோம். இவர்களின் லயிப்பு படைத்த இறைவனை விடுத்து படைப்பினங்களிடம் செல்ல வைத்து விட்டது. எனவே இசையையும் கவிதையையும் ஒரு அளவோடு ரசிக்க பழகிக் கொள்ள வேண்டும்.

    நீங்கள் கொடுத்த மற்ற நான்கு பேரும் திறமைசாலிகள். அதில் அப்துல் கலாம் மாத்திரம் இளமையில் பிராமணர்களோடு அதிகம் இருந்ததால் இந்து மதத்தையும் சில நேரம் போட்டு குழப்பிக் கொள்வார். மற்றபடி நாட்டுப் பற்று மொழிப் பற்று இவற்றில் குறை காண முடியாது.

    //இல்லையெனில் பரிணாம் செய்லாக்க முறை மூலம் பல கடினமான் முடிவெடுக்கும் புதிர்கள் விடை காண இயலும்,இது அதிக பயன்பாடுள்ள கணித முறை, பரிணாம கொள்கையின் மாதிரி என்பதை மனதில் இருத்தினால் போதுமானது.//

    ரொம்ப சிரமப்பட்டு பரிணாமத்தை நிலை நிறுத்த முயற்சி எடுக்கிறீர்கள். அஸ்திவாரம் பலமாக இல்லாததால் நீங்கள் கட்டும் கட்டடம் அவ்வப்போது சரிந்து விடுகிறது. இருந்தாலும் முயற்சி செய்யுங்கள். நம்பிக்கையில்தானே மனிதனின் வாழ்க்கையே ஓடுகிறது. :-)

    ReplyDelete
  3. வாங்க சகோ சுவனன்,

    இது ஆஸ்கார் பற்றி மட்டுமல்ல என்பதை இருவரும் அறிவோம்.ஒரு மதம் என்றால் அதில் பல் பிரிவுகளும் ,பல்வேறுபட்ட நடைமுறைகளும் இருப்பது மிக இயல்பான வழக்கமே.மதம் பின்பற்றுபவர்கள் ஒவோருவருக்கும் தன் பிரிவு மட்டுமே சரியாக படுவது இயல்பே.

    ரஹ்மான் எப்படி வழிபடுகிறார் என்பது அவ்ருடைய தனிப்பட்ட விருப்பம்.அதிகப்ட்சம் நீங்கள் என்ன செய்யலாம் என்றால் உங்களிடம் ஆலோசனை கேட்டால் சொல்ல்லாம்.அல்லது பிரர்த்தனை மூலம் தூது விடுங்கள்.சரி த்வறு என்று மதப் பிரிவுகளில் கூற இயலாது என்பது என் கருத்து.

    "உமறுப்புலவரின் சீறாப்புராணம் குறித்த எரிச்சல் என்னல் புரிந்து கொள்ள முடிகிறது".இது வரலாறு நம் முன்னோர்கள் இப்படித்தான் மதம் பின்பற்றினார்கள் என்பது வரலாறு!!!!!!!!!!.

    என்க்கும் உங்களின் மத அறிவியல் என்பது வார்த்தை விளையாட்டு என்பதும் 1400+ வருடங்களாக் இல்லாத பொருள் கூறுகிறீர்கள் என்பது ஏமாற்று வேலையாக தெரிகிறது என்பதற்காக அப்ப்டி செய்யாதே என கூற மாட்டேன்!!!!!!!

    நாட்டின் சட்ட திட்டங்களுக்கு உட்பட்ட எதனையும் ஒருவர் செய்ய உரிமை உண்டு.

    ஒரு விடயத்தை இப்படித்தான் செய்ய வேண்டும் என்பது வன்முறை.இப்போது ஏஎன் தினமும் மதப்பிரிவினரின் இடையே வன்முறை வெடிக்கிறது என்ற கேள்விக்கு விடை அனைவரும் அறியும் வாய்ப்பு அளித்தமைக்கு நன்றி.

    பாகிஸ்தானின் அப்துஸ் சலாம் பற்றி கூறவில்லை.இவர் ஒரு அஹமதியா,ஆனால் உங்களை விட தன் நோபெல் பரிசை இறைவனின்
    படைப்பின் ஒரு முடிச்சை அவிழ்ழ்க்க முடிந்தது என கூறியவர்.
    இந்த கருத்து என்க்கு உடன்பாடு இல்லை எனினும் அவரின் கண்டுபிடிப்பு மிக மகத்தானது.

    இவரைப் பற்றி எதுவும் கூறவில்லையே!!!!!

    அடிக்கடி வாருங்கள்.

    நன்றி

    ReplyDelete
  4. //ரொம்ப சிரமப்பட்டு பரிணாமத்தை நிலை நிறுத்த முயற்சி எடுக்கிறீர்கள். அஸ்திவாரம் பலமாக இல்லாததால் நீங்கள் கட்டும் கட்டடம் அவ்வப்போது சரிந்து விடுகிறது. இருந்தாலும் முயற்சி செய்யுங்கள். நம்பிக்கையில்தானே மனிதனின் வாழ்க்கையே ஓடுகிறது. //
    பரிணாம்த்தை நான் நிலை நிறுத்துகிறேனா!!!!!.ஏதோ கற்பதை கொஞ்சம் எளிமையாக் சொல்லும் முயற்சி! அவ்வளவுதான் சகோ!!!!!!

    என்மீது உங்களுக்கு மிக்க அன்பு உண்டு என்பதை அறிவேன்.அதனால்தான் என்னை மிக அதிக்மாக் புகழுகிறீர்கள்.

    "பரிணாம் கொள்கை சார்ந்த எல்லா புகழும் என் தாத்தா டார்வினுக்கே"

    டிஸ்கி
    சீக்கிர‌ம் ஒரு பரிணாம் எதிர்ப்பு பதிவு போட ஏற்பாடு செய்யுங்கள்.போர் அடிக்குது!!!!!!!
    நன்றி

    ReplyDelete
  5. சகோ, உங்க பரிணாம பதிவை ஆவலாக படிப்பதோடு வஹாபிகளுக்கு பிடிக்காத ஆறு விசயங்களையும் படிக்கிறோம். அவங்களுக்கு நல்லிணக்கம் என்ற சொல் அலர்ஜி.

    ReplyDelete
  6. வாங்க சகோ குயிக்ஃபாக்ஸ்,

    தமிழ் பதிவுலகில் கலகல்ப்பு ஏற்படுத்தும் அனைத்து வஹாபி சகோக்களுக்கும் இந்த பாராட்டுகளில் குறிப்பாக அன்பு சகோதரர் சுவ‌னன் அவர்களுக்கும் பங்கு உண்டு!.ஒன்றை ஒன்று சார்ந்து வாழும் உயிரின சங்கிலியில் ஏற்படும் ஆயுதப் போட்டி என்ற பரிணாம் செயலையே இது விள்க்குகிறது.

    அவர்களுக்கு எங்கும் எதிலும் பராபரம் தெரிவது போல் நம்க்கு பரிணாம‌ம் தெரிகிறது!

    வருகைக்கும் கருத்துக்கும் நன்றி!

    ReplyDelete
  7. நண்பரே இரண்டு நாட்களாக, ஏதாவது புரியுமா என்று படித்து கொஞ்சம் புரிந்து மண்டைக் காய்ந்தது தான் மிச்சம். கோட்பாடு புரிந்தது.

    ReplyDelete
  8. கையிலெ பை, கழுத்திலே டை, வாயிலே பொய் (just joking)மனிதர்களின் சுலப வேலைக்காக ஒரு கணிதமே ஏற்படுத்திய W.R.Hamiltonக்கு ஒரு கோயிலை அவர்கள் கட்டலாம்.

    ReplyDelete
  9. நண்பர் நரேன்
    கோட்பாடு புரிந்து மற்றவை மென்பொருள்[software] எழுத முற்ட்படாலோ,அல்லது பய்ன் படுத்தினால் மட்டுமே புரியும்.இந்த தேர்வு,கல்ப்பு,சிறு மாற்றம் எப்படி குழுத் தேர்வுகளில் ஏற்படுத்துவது என்பதும் ஒவொரு தலைமுறையாக் ஒரு லூப் ஆக எழுதி விட்டால் முடிந்தது.இவை அனைத்துமே அணி அல்லது array சார்ந்த செயல்கள் என்பதை நீங்கள் அறியலாம்.
    இப்புதிரில் ஆய்வு செய்து பலர் முனைவர்[ டாக்ரடேட்] பட்டம் பெற்று உள்ளதை கூறவும் விரும்புகிறேன்.

    இப்போது கோட்பாடு மட்டும் புரிந்தால் போதுமானது.

    இயற்கை நாடினால் இந்த அல்காரிதம் பற்றியே எளிமையான‌ தொடர்,மென்பொருள் பயன்பாட்டுடன் எழுதுவோம்!

    முதலில் அ.வ முடியட்டும் பிறகு மூலக்கூறு அறிவியலும் பரிணாம‌மும் பிறகு இது அப்புறம்..........

    நன்றி

    ReplyDelete
  10. Dear naren

    we[Homo sapiens] invented mathematics because we are lazy!!!!!!!

    Hi Hi
    bye!!!!!!!!!

    ReplyDelete