శాస్త్ర విజ్ఞానము ఇప్పుడు మిగతా భారతీయ భాషల్లో కూడా... ఇక్కడ నొక్కి చూడండి. For Science in other Indian Languages. Please Click here.

చీమలు పరిష్కరించిన ఇంజినీరింగ్ సమస్యలు

Posted by శ్రీనివాస చక్రవర్తి Sunday, April 4, 2010

దారంతా ఫీరొమోన్ చల్లడం వల్ల ఒక చీమ కనుక్కున్న దారి ఇతర చీమలకి తెలిసిపోతుందని కిందటి పోస్ట్ లో చూశాం. ఈ చిన్న పద్ధతి సహాయంతో ఆహార వనరులకి అతిదగ్గరి దారులని చీమలు ఎలా కనుక్కుంటాయో చూద్దాం.

A అనే బిందువు వద్ద రెండు చీమలు ఉన్నాయని అనుకుందాం. B అనే బిందువు వద్ద కొంత ఆహారం ఉంది. A, B లని కలుపుతూ ఒక దగ్గరి దారి, S, మరో చుట్టు దారి L ఉన్నాయని అనుకుందాం. S ని అనుసరించి ఒక చీమ A నుండి B కి వెళ్లి తిరిగి వచ్చే దారిలో ఫిరొమోన్ చల్లుకుంటూ వచ్చింది. రెండవ చీమ చుట్టుదారి అయిన L వెంట A నుండి B కి వెళ్లి తిరిగి వచ్చే దారిలో ఫిరొమోన్ చల్లుకుంటూ వచ్చింది. ఈ ఫిరొమోన్ తో మరో విషయం ఏంటంటే ఒకసారి చల్లబడ్డ ఫిరొమోన్ క్రమంగా ఆవిరవుతూ ఉంటుంది.

మొదటి చీమ నడిచిన దారి S చిన్నది కనుక ఆ దారి మీద ఒక యూనిట్ దూరంలో చల్లబడే ఫిరొమోన్ L మీద కన్నా కాస్త ఎక్కువగా ఉంటుంది. కనుక రెండు చీమలూ తిరిగి A ని చేరుకున్నాక చూస్తే S మీద L మీద కన్నా కాస్త ఎక్కువ ఫిరొమోన్ మిగిలి ఉంటుంది. ఇప్పుడు మరో మూడో చీమ A దగ్గర్నుండి బయలుదేరుతూ, S వెంట వెళ్లాలా, L వెంట వెళ్లాలా అని మీమాంసలో పడ్డప్పుడు, ఎటుపక్క నుండి ఘాటైన ఫిరొమోన్ గంథం వస్తోందో చూసుకుంటుంది. S లో ఎక్కువ ఫిరొమోన్ ఉంది కనుక S ని ఎంచుకుంటుంది. మూడవ చీమ నడిచి వచ్చాక S మీద ఫిరొమోన్ సాంద్రత మరింత పెరుగుతుంది. ఇలా కొంతకాలం పోయాక L మీద అసలు ఫిరొమోన్ వాసనే మిగలదు. S మీద బాగా ఎక్కువ అవుతుంది. రెండు దారులలో దగ్గరి దారి ఏదో అప్పట్నుంచి ’వాసన చూసి’ పట్టేయొచ్చు. ఈ ప్రక్రియ వల్ల తొలిదశల్లో రెండు దారులలో ఉండే ఫిరొమోన్ సాంద్రతలో ఉండే సూక్ష్మమైన భేదం పోగా పోగా మరింత వృద్ధి చెందుతుంది. ఇలాంటి పరిణామాన్నే positive feedback అంటారు. చీమలలో ఇలా దగ్గరి దారులు కనుక్కునే సామర్థ్యాన్ని డెనోబోర్గ్ తదితరులు (Deneubourg et al 1990) గమనించారు.

చీమల యొక్క ఈ ప్రత్యేక సామర్థ్యాన్ని చూసి స్ఫూర్తి చెందిన ఇంజినీర్లు ఈ పద్ధతిని గ్రాఫ్ థియరీ కి చెందిన కొన్ని కఠినమైన సమస్యల మీద ప్రయోగించారు. అలాంటి సమస్యల్లో ’ప్రయాణించే సేల్స్ మాన్ సమస్య’ (Traveling salesman problem) ఒకటి. ఈ సమస్యలో ఒక సేల్స్ మన్ కొన్ని (N) ఊళ్లు చుట్టి రావాలి. ఊళ్ల మధ్య దూరాలన్నీ సేల్స్ మన్ కి తెలుస్. అయితే కొన్ని నిబంధనలు పాటించాల్సి ఉంటుంది. ఒకసారి సందర్శించిన ఊరిని మళ్లీ సందర్శించకూడదు. ఏ ఒక్క ఊరిని వదల కూడదు. ప్రయాణించిన దారి పొడవు సాధ్యమైన అన్ని దారుల కన్నా చిన్నది కావాలి. సాధ్యమైన ప్రతీ దారిని పరిగణించి, వాటిలో అన్నిటికన్నా చిన్న దారిని ఎంచుకోవాలంటే ఈ సమస్య చాలా కఠినం అవుతుంది. ఎందుకంటే N ఊళ్లు ఉన్నప్పుడు, ఒక ఊళ్లో బయలుదేరి చివరికి అదే ఊరికి తిరిగి రావడానికి మొత్తం (N-1)! మార్గాలు ఉన్నాయి. N పెద్దది అవుతున్న కొలది ఈ సంఖ్య చాలా వేగంగా పెరిగిపోతుంది. కంప్యూటర్ సైన్స్ లో అత్యంత కఠినమైన సమస్యల్లో ఈ సమస్య ఒకటి. ఈ సమస్యకి మరో ప్రత్యేకత కూడా ఉంది. ఇది ఒక ప్రత్యేక సమస్య కాదు. ఒక ప్రత్యేక జాతికి చెందిన సమస్యలకి ఇది ప్రతినిధి. కనుక ఈ సమస్యని వేగంగా, సమర్థవంతంగా పరిష్కరించడం ఎలాగో తెలిస్తే, ఆ పరిష్కారం ఆ జాతికి చెందిన సమస్యలన్నిటికీ వర్తిస్తుంది.

ఈ సమస్యని ’చీమలపద్ధతి’లో చేసే విధానాలు ఇలా ఉంటాయి. (ఇవన్నీ కంప్యూటర్ సిములేషన్ ద్వారా చేసేవే నని, ఈ ప్రయోగాలు నిజం చీమల్తో చెయ్యరని గుర్తుంచుకోవాలి!) ఇందులో కొన్ని ’చీమల’ని ఆ ఊళ్లన్నీ చుట్టి రమ్మని విడిచిపెడతారు. ప్రతీ చీమ కొన్ని నిబంధనలని అనుసరిస్తూ ఆ ఊళ్లన్నీ చుట్టి వస్తుంది. ఆ చుట్టే దారిలో కొన్ని సూత్రాలని అనుసరిస్తూ ఆయా దారుల వెంట ఫిరొమోన్ చల్లుకుంటూ వస్తుంది. తరువాత వచ్చే చీమ చేసే యాత్రని ఈ ఫిరొమోన్ ప్రభావితం చేస్తుంది. చీమలు అనుసరించే నియమాలు ఇవి:

1 . ఒక ఊరిని ఒకసారే సందర్శించాలి.
2. దగ్గరిగా ఉన్న ఊళ్ల కన్నా దూరంగా ఉన్న ఊళ్లని సందర్శించే సంభావ్యత (probability) తక్కువగా ఉంటుంది.
3. రెండు ఊళ్ల మధ్య ఫిరొమోన్ సాంద్రత ఎంత ఎక్కువ ఉంటే, చీమ ఆ దారిని ఎంచుకునే సంభావ్యత అంత ఎక్కువ అవుతుంది.
4. చీమ తాను చుట్టి వచ్చిన దారులలో ఫిరొమోన్ చల్లుకుంటూ వస్తుంది.
5. చీమ ఒక చుట్టు చుట్టి వచ్చిన ప్రతీ సారి దారుల మీద ఉన్న ఫిరొమోన్ కొద్దిగా ఆవిరి అవుతుంది.

పై నియమాలని అనుసరించి చీమలు ఊళ్ల న్నీ చుట్టు చుట్టి వస్తుంటే కొన్ని పర్యాయాల తరువాత బాగా తక్కువ పొడవు ఉన్న మార్గంలో బాగా ఎక్కువ ఫిరొమోన్ మిగులుతుంది.
ఈ ant algorithms కి కంప్యూటర్ నెట్వర్క్స్ లో, ట్రాఫిక్ నియంత్రణలో ఇలా ఎన్నో వాస్తవ ప్రపంచ సమస్యలలో ప్రయోగించి చక్కని ఫలితాలు సాధించారు. మరిన్ని వివరాల కోసం ఈ కింది వనరులని సంప్రదించగలరు.

References:
http://en.wikipedia.org/wiki/Ant_colony_optimization#cite_note-S._Goss-2
M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
J.-L. Deneubourg, S. Aron, S. Goss et J.-M. Pasteels, The self-organizing exploratory pattern of the Argentine ant, Journal of Insect Behavior, volume 3, page 159, 1990

3 comments

  1. home page Says:
  2. చీమ సిద్దాంతాన్ని చాలా బాగా వివరించారు

     
  3. jeevani Says:
  4. నాగ ప్రసాద్ గారూ, ఇవి పుస్తకంగా ఏమైనా వేశారా? వేస్తున్నారా? ఆ ఆలోచన లేకపోతే ఇలాగే ప్రింట్ తీసుకుని బౌండ్ చేయిద్దాం అనుకుంటున్నాను. లేదా స్పైరల్ బైండింగ్.

     
  5. జీవని గారు,
    వ్యాసాలు మీరు ప్రిన్టవుట్ తీసుకుని వ్యక్తిగతంగా వాడుకోవచ్చు. అయితే దయచేసి సముచిత రీతిలో క్రెడిట్స్ ఇవ్వండి.
    వీటిని పుస్తకాలుగా మార్చే ప్రయత్నం జరుగుతోంది. మీకు కావాలంటే కొన్ని పుస్తకాలు ఉచితంగా పంపగలను. పెద్ద మొత్తంలో కావాలంటే దయచేసి ప్రచురణకర్తని సంప్రదించండి.
    ప్రచురణ కర్త వెబ్సైట్:
    http://www.manchipustakam.in/

     

Post a Comment

postlink

సైన్సు పుస్తకాలు ఇక్కడ నుంచి కొనవచ్చు.. click on image

అంతరిక్షం చూసొద్దాం రండి

"తారావళీ సూపర్ ట్రావెల్స్" తరపున స్వాగతం... సుస్వాగతం!" "తారావళీ సూపర్ ట్రావెల్స్" గురించి ప్రత్యేకించి మీకు చెప్పనవసరం లేదు. తారాంతర యాత్రా సేవలు అందించడంలో మాకు 120 ఏళ్ల అనుభవం ఉంది. మా హెడ్ క్వార్టర్స్ భూమి మీదే ఉన్నా, సౌరమండలం బయట మాకు చాలా బ్రాంచీలు ఉన్నాయని మీకు బాగా తెలుసు. అంతరిక్షానికి వెళ్ళడానికి ఇక్కడ నొక్కండి

Printer-friendly gadget

Print

ఈ బ్లాగులోని పోస్ట్ లు ఆటోమేటిక్ గా మీ మెయిల్ ఇన్బాక్స్ లోకి చేరడానికి మీ ఈ-మెయిల్ ఐడీని ఎంటర్ చేసి చందాదారులు కండి Enter your email address:

Delivered by FeedBurner

Total

Blogumulus by Roy Tanck and Amanda FazaniInstalled by CahayaBiru.com

Label Category

Followers

archive

Total Pageviews

There was an error in this gadget
There was an error in this gadget

విజ్ఞానులు

GuestBooker 2.5

Recent Posts

Popular Posts

Follow by Email