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

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

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

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

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

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

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

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

http://en.wikipedia.org/wiki/Travelling_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

http://www.ceng.metu.edu.tr/~ucoluk/research/publications/tspnew.pdf

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

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

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

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

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

நன்றி