پایان نامه ارائهء يک الگوريتم جستجوي مبتنی بر روشهای مبني برجمعيت در بهينه سازي ترکيبي
فهرست مطالب
- مقدمه …………………………………………………………………………………………………………. 3
2 . انواع سيستم هاي نرم افزاري…………………………………………………………………………………………………………….. 3
- 1. سيستم تصميم يار(DSS)…………………………………………………………………………………………………………….. 4
- 1. 1. ويژگيها و قابليتهاي DSS ………………………………………………………………………………………………………… 5
- 1. 2. زيرسيستم هاي DSS ……………………………………………………………………………………………………………… 6
- 2. سيستم خبره………………………………………………………………………………………………………………………………… 6
- 2. 1. ساختار سيستم هاي خبره …………………………………………………………………………………………………………. 6
- بهينه سازي در سيستم هاي رابطه اي ………………………………………………………………………………………………… 7
- 1. مروري بر پردازش پرس و جو ………………………………………………………………………………………………………… 7
- 2. بهينه سازي پرس و جو………………………………………………………………………………………………………………….. 8
- جستجو……………………………………………………………………………………………………………………………………………. 9
- 1. روشهاي جستجوي ساخت يافته……………………………………………………………………………………………………… 9
- 1. 1. جستجوي اول بهترين……………………………………………………………………………………………………………….. 9
- 1. 1. 1. کمينه کردن هزينه تخميني براي رسيدن به يک هدف : جستجوي حريصانه………………………………. 9
- 1. 1. 2. کمينه کردن هزينه کل مسير: جستجوي A*…………………………………………………………………………. 10
- 1. 2. جستجو با حافظه محدود………………………………………………………………………………………………………….. 10
- 1. 2. 1. جستجوي A* عمقي تکراري (IDA*)………………………………………………………………………………… 10
- 1. 2. 2. جستجوي A* ساده شده با محدوديت حافظه SMA*))……………………………………………………….. 10
- 1. 3. الگوريتم هاي بهبود تکرار شونده………………………………………………………………………………………………… 11
- 1. 4. الگوريتم ژنتيک……………………………………………………………………………………………………………………….. 11
- 2. جستجوي توزيع شده (الگوريتمهاي جستجو در عاملها)……………………………………………………………………. 12
- 2. 1. تعريف مساله ارضاي محدوديت (CSP)…………………………………………………………………………………….. 13
- 2. 2. الگوريتم تصفيه………………………………………………………………………………………………………………………… 14
- 2. 3. الگوريتم سازگاري برمبناي فرااستدلال……………………………………………………………………………………….. 15
- 2. 4. عقبگرد آسنکرون……………………………………………………………………………………………………………………… 16
- 2. 5. جستجوي الزام ضعيف آسنکرون………………………………………………………………………………………………… 16
- 3. مساله يافتن مسير………………………………………………………………………………………………………………………… 16
- 3. 1. تعريف مساله يافتن مسير………………………………………………………………………………………………………….. 16
- 3. 2. برنامه نويسي پوياي آسنکرون……………………………………………………………………………………………………. 17
- 3. 3. A* بي درنگ يادگير(LRTA*)……………………………………………………………………………………………… 17
- 3. 4. A* بي درنگ(RTA*)…………………………………………………………………………………………………………… 18
- 3. 5. جستجوي هدف متحرک(MTS)……………………………………………………………………………………………… 18
- 3. 6. جستجوي دوطرفه بي درنگ(RTBS)………………………………………………………………………………………. 19
- 3. 7. جستجوي چندعامله بي درنگ…………………………………………………………………………………………………… 21
- 4. بازيهاي دو نفره……………………………………………………………………………………………………………………………. 22
- 4. 1. فرموله کردن بازيهاي دو نفره…………………………………………………………………………………………………….. 22
- 4. 2. رويه Minimax…………………………………………………………………………………………………………………….. 22
- 4. 3. هرس β-α…………………………………………………………………………………………….. 22
- فرااکتشافات در بهينه سازي ترکيبي…………………………………………………………………………………………………… 23
- 1. تعاريف اوليه ……………………………………………………………………………………………………………………………….. 23
- 2. طبقه بندي فرااکتشافات……………………………………………………………………………………………………………….. 26
- 3. روشهاي خط سير………………………………………………………………………………………………………………………… 27
- 3. 1. جستجوي محلي پايه……………………………………………………………………………………………………………….. 28
- 3. 2. آنيلينگ شبيه سازي شده…………………………………………………………………………………………………………. 28
- 3. 3. جستجوي ممنوع……………………………………………………………………………………………………………………… 30
- 3. 4. روشهاي جستجوي محلي کاوشگرانه………………………………………………………………………………………….. 31
- 3. 4. 1. GRASP………………………………………………………………………………………………………………………….. 31
- 3. 4. 2. جستجوي همسايگي متغير…………………………………………………………………………………………………… 31
- 3. 4. 3. جستجوي محلي هدايت شده………………………………………………………………………………………………… 32
- 3. 4. 4. جستجوي محلي تکراري………………………………………………………………………………………………………. 33
- 4. روشهاي مبني بر جمعيت……………………………………………………………………………………………………………… 33
- 4. 1. محاسبه تکاملي……………………………………………………………………………………………………………………….. 33
- 4. 1. 1. جستجوي پخشي و اتصال مجدد مسير…………………………………………………………………………………… 36
- 4. 1. 2. الگوريتم هاي تقريب توزيع……………………………………………………………………………………………………. 37
- 4. 2. بهينه سازي گروه مورچه ها(ACO)…………………………………………………………………………………………. 37
- 5. ديدگاه متمرکزسازي و متنوع سازي……………………………………………………………………………………………….. 38
- 5. 1. متمرکزسازي و متنوع سازي……………………………………………………………………………………………………… 39
- 5. 2. کنترل استراتژيک متمرکزسازي و متنوع سازي…………………………………………………………………………… 39
- 5. 3. ترکيب فرااکتشافات………………………………………………………………………………………………………………….. 40
- خلاصه و نتيجه گيري……………………………………………………………………………………………………………………….. 43
- مراجع…………………………………………………………………………………………………………………………………………….. 44
- مقدمه
در اين ضميمه ابتدا معرفي بهينه سازي و سپس به معرفي تکنيک هاي مورد استفاده در سيستم هاي نرمافزاري پرداخته و تمرکز مطالب بر روي تکنيک جستجو قرار مي گيرد.
يکي از (و قطعاُ مهمترين) مفاهيم مطرح در تحقيق عمليات مفهوم بهينه سازي[1] است. بهينه سازي را ميتوان تخصيص منابع به مصارف به بهترين شکل ممکن تعريف کرد. نکته اساسي در اين تعريف رسيدن به بهترين تخصيص ممکن است، بطوريکه تخصيصي بهتر از آن وجود نداشته باشد. استفاده از روشهاي اوليه بهينه سازي شامل برنامه ريزي خطي[2]، برنامه ريزي عدد صحيح[3]، برنامه ريزي پويا[4]، و برنامه ريزي غير خطي[5] با مشکلاتي همراه بود و مهمترين اين مشکلات وقتگير بودن حل مسائل بزرگ با آنها بود. به گونه اي که حتي با تکنولوژيهاي محاسباتي پيشرفته امروزي حل يک مساله با ابعاد وسيع با تکنيکهاي ذکر شده به چندين سال زمان نياز دارد. بروز اين مشکل به توهماتي که در ابتداي شکل گيري دانش تحقيق در عمليات، مبني بر حل بهينه تمام مسائل دنيا با استفاده از اين دانش، ايجاد شده بود پايان داد. بروز اين مشکل، همچنين، سبب شد محققان مجبور به تعديل انتظارات خود از اين دانش جديد در يافتن بهترين جواب ممکن شوند و به جوابهايي به اندازه کافي خوب، که حتي درمورد مسائل با ابعاد بزرگ نيز در مدت زمان منطقي ميتوان به آنها رسيد، اکتفا کنند.
2 . انواع سيستم هاي نرم افزاري
نرم افزار مي تواند به هر موقعيتي که در آن مجموعه مراحل رويه اي خاصي به نام الگوريتم تعريف مي شود، اطلاق گردد ( به استثناي نرم افزارهاي سيستم هاي خبره و شبکه هاي عصبي ). توسعه مقولات کلي بامعني براي کاربردهاي نرمافزاري تا حدي مشکل است. با رشد پيچيدگي نرم افزار مرزبندي بسيار دقيق نرم افزارها، ناپديد مي گردد. نواحي نرم افزاري زير، وسعت کاربردهاي بالقوه را نشان مي دهد :
- نرم افزار سيستمي : نرم افزار سيستمي، مجموعه اي از برنامه هاست که براي خدمت رساني به ساير برنامه ها نوشته شده است. بعضي نرم افزارهاي سيستمي (مانند کامپايلرها و ويرايشگرها) ساختارهاي اطلاعاتي پيچيده ولي محدودي را پردازش مي کنند. ساير کاربردهاي سيستمي (مانند اجزاي سيستم عامل، درايورها و پردازشگرهاي ارتباطات راه دور) داده هاي نامحدود گسترده اي را پردازش مي نمايند. در هر دو مورد، حوزه نرم افزار سيستمي، توسط اين ويژگي ها تعيين مي گردد، تعامل زياد با سخت افزار، استفاده زياد توسط چندين کاربر، عمليات همروند که نياز به زمانبندي، مديريت منبع و مديريت پردازش دارد، ساختار داده هاي پيچيده و رابطهاي خارجي چندگانه.
- نرم افزار بي درنگ : نرم افزاري که رويدادهايي که در جهان واقع اتفاق مي افتد را کنترل، نظارت و تحليل ميکند. عناصر نرم افزار بي درنگ شامل بخش جمع آوري کننده اطلاعات (که اطلاعات را از محيط خارجي جمع آوري و شکل دهي مي کند)، بخش تحليل (که اطلاعات را به شکل موردنياز کاربر تبديل مي کند) و بخش کنترل/خروجي که به محيط خارج پاسخ داده و بخش نظارت است که ساير بخشها را به گونه اي هماهنگ ميکند که پاسخ بيدرنگ ( بين 1 ميلي ثانيه تا 1 ثانيه) فراهم شود.
- نرم افزار تجاري : پردازش اطلاعات تجاري بزرگ ترين حوزه کاربرد نرم افزاري است. اين سيستمهاي مديريت اطلاعات به يک يا چند پايگاه داده بزرگ اطلاعات تجاري دسترسي دارند.کاربردهاي اين حوزه، داده هاي موجود را به روشي ساختاردهي مجدد مي کنند که عمليات تجاري يا تصميم گيري مديريتي را تسهيل کنند. علاوه بر کاربرد پردازش داده مرسوم، کاربردهاي نرم افزار تجاري، محاسبات متعامل را هم شامل مي شوند.
- نرم افزار علمي و مهندسي : اين نوع نرم افزار توسط الگوريتم هاي معمول عددي مشخص ميگردند ولي کاربردهاي جديد حوزه علمي و مهندسي، از الگوريتم هاي عددي مرسوم دور مي گردند. طراحي به کمک کامپيوتر، شبيه سازي سيستم و ساير کاربردهاي متعامل به تدريج به ويژگيهاي نرم افزار سيستمي و بي درنگ اضافه مي شوند.
- نرم افزار نهفته : محصولات هوشمند امروزه بسيار رايجند. نرم افزار نهفته، در حافظه خواندني قرار مي گيرد و براي کنترل محصولات و سيستم ها به کار مي رود. سيستم نهفته مي تواند اعمال اختصاصي و خيلي محدودي را انجام دهد و يا عملکرد و قابليت کنترل کافي را فراهم مي نمايد ( مثل توابع ديجيتال در اتومبيل مانند کنترل سوخت و سيستم هاي ترمز )
- نرم افزار کامپيوترهاي شخصي : فروش نرم افزار کامپيوتر شخصي، در طول دو دهه گذشته رونق گرفته است. پردازش کلمه، صفحه گسترده ها، گرافيک کامپيوتري، چندرسانه اي، سرگرمي، مديريت پايگاه داده، کاربردهاي مالي تجاري و شخصي و دسترسي به پايگاه داده تعداد اندکي از اين کاربردهاست.
- نرم افزار مبتني بر وب : صفحات وب بازيابي شده توسط کاوشگر، نرم افزاري است که دستورات اجرايي و داده را به کار مي برد. در اصل شبکه به يک کامپيوتر عظيم تبديل شده که منبع نرم افزاري تقريبا نامحدودي را فراهم ميکند که مي تواند توسط يک مودم براي همه در دسترس باشد.
- نرم افزار هوش مصنوعي : اين نرم افزارها از الگوريتم هاي غيرعددي براي حل مسايل پيچيده که براي محاسبه و تحليل ساده و سرراست نيستند، بهره مي برند. سيستم هاي خبره که سيستم هاي مبتني بر دانش هم ناميده ميشوند، تشخيص الگو (تصوير و صوت)، شبکه هاي عصبي هوشمند و بازيها، کاربردهاي رايجي دراين مقوله هستند[1].
- 1. سيستم تصميم يار[6](DSS)
تعاريف اوليه DSS، آن را به عنوان سيستمي معرفي مي کرد که براي پشتيباني از تصميم گيرندگان مديريتي در موقعيت هاي تصميم گيري شبه ساختاريافته به کار مي رفتند. DSS دستياري براي تصميم گيرندگان بود که قابليتهاي آنان را توسعه مي داد ولي جايگزين قضاوت آنان نمي شد. بخش ديگري از تعريف، متذکر مي شد که سيستم مي تواند مبني بر کامپيوتر باشد، مي تواند به صورت درون خطي[7] و متعامل عمل کند وترجيحا قابليت خروجي گرافيکي داشته باشد.
Little، DSS را به شکل ” مجموعه رويه هاي مبني بر مدل براي پردازش داده ها و قضاوت جهت کمک به مدير در تصميم گيري ” تعريف مي کند. چنين سيستمي براي موفقيت بايد ساده، قدرتمند، داراي کنترل آسان، وفق پذير، کامل در جنبه هاي مهم و راحت براي برقراري ارتباط باشد. آنچه در اين تعريف به طور ضمني ديده مي شود، اين است که سيستم، مبني برکامپيوتر است و سرورها توسعه اي از قابليتهاي حل مساله کاربران هستند.
Moore و Chung چنين بحث مي کنند که مفهوم ساختارمندي که بخشي از بيشتر تعاريف اوليه DSS است (به اين معني که DSS مي تواند موقعيتهاي نيمه ساختيافته و ساخت نيافته را اداره کند )، به طور کلي معني ندارد. يک مساله مي تواند فقط با توجه به تصميم گيرنده خاص، تحت عنوان ساختاريافته يا نيافته توصيف گردد (يعني تصميمات ساختاريافته به اين دليل ساختيافته اند که ما به اين شکل با آنها برخورد کرده ايم). بنابراين آنها DSS را سيستم هاي قابل توسعه اي تعريف مي کنند که توانايي پشتيباني از تحليل داده هاي ad hoc و مدل سازي تصميم، با گرايش به سمت برنامه ريزي آينده و به کاررفته در بازه هاي برنامه ريزي نشده و نامنظم را داراست.
Bonczek، DSS را به عنوان سيستم مبني بر کامپيوتري تعريف مي کند که شامل سه مولفه متعامل است. يک سيستم زباني (مکانيزم برقراري ارتباط بين کابر و ساير مولفه ها)، يک سيستم دانشي (يک ذخيره دانش نهفته در سيستم در رابطه با مساله) و سيستم پردازش مساله (پيوند بين دو مولفه ديگر).
سرانجام Ken، لغت DSS را براي موقعيتهايي که يک سيستم نهايي تنها از طريق يک پردازش تطبيقي يادگيري و ارزيابي مي تواند توسعه يابد، به کار مي برد.
به عنوان يک تعريف کلي مي توان گفت DSS يک سيستم متعامل، انعطاف پذير و وفق پذير است که به طور ويژه براي پشتيباني از راه حل مشکلات مديريتي ساختارنيافته جهت تصميم گيري بهتر، توسعه يافته است. اين سيستم از دادهها استفاده مي کند، رابط کاربر ساده اي فراهم مي کند و مي تواند ديدگاه تصميم گيرندگان را هم در تصميم گيري شرکت دهد. به علاوه DSS مدلها را به کار مي برد، توسط يک پردازش تعاملي ساخته مي شود، از تمام فازهاي تصميم گيري پشتيباني مي کند و مي تواند شامل يک مولفه دانش باشد.
- 1. 1. ويژگيها و قابليتهاي DSS
- DSS، عمدتا در موقعيتهاي نيمه ساختيافته و ساختارنيافته با همراه کردن قضاوت انسان و اطلاعات کامپيوتري، از تصميم گيرندگان پشتيباني مي کند. چنين مسايلي نمي توانند (يا به راحتي نمي توانند) باساير سيستم هاي کامپيوتري يا روشها و ابزارهاي کمي استاندارد، حل شوند.
- اين پشتيباني شامل سطوح مختلف مديريتي (از مديران اجرايي سطح بالا تا مديران رده معمولي) مي باشد.
- اين پشتيباني براي افراد هم مانند گروهها فراهم مي شود.
- اين پشتيباني براي چندين تصميم داراي وابستگي و/ يا ترتيبي فراهم مي گردد.
- DSS از کليه فازهاي فرايند تصميم گيري پشتيباني مي کند : هوش، طراحي، انتخاب و پياده سازي.
- از فرايندها و سبکهاي متنوع تصميم گيري پشتيباني مي کند.
- DSS با زمان تطبيق پذير است. تصميم گيرنده ممکن است واکنش دهنده و قادر به رويارويي سريع با شرايط متغير باشد و DSS را براي برخورد با اين تغييرات آماده کند. DSS، انعطاف پذير است بنابراين کاربران ميتوانند عناصر پايه اي را اضافه، حذف، ترکيب، تغيير يا مرتب سازي دوباره کنند.
- کاربران با آن احساس راحتي کنند. کابرپسندي، قابليت گرافيک قوي، رابط انسان- ماشين متعامل به زبان انگليسي مي تواند اثربخشي DSS را به شدت افزايش دهد.
- DSS به جاي کارايي (هزينه) تصميم گيري، براي بهبود اثر تصميم گيري تلاش مي کند ( دقت، زمانبندي و کيفيت ).
- تصميم گيرنده کنترل کامل بر کليه مراحل فرآيند تصميم گيري حل مساله دارد. هدف DSS پشتيباني و نه جايگزيني تصميم گيرنده است.
- کاربران نهايي خودشان مي توانند قادر به ساخت و تصحيح سيستم هاي ساده باشند.
- DSS معمولا با مدلها به تحليل موقعيتهاي تصميم گيري کمک مي کند.
- DSS مي تواند به منابع داده اي، قالبها و انواع متفاوت، دسترسي داشته باشد. از سيستم هاي جغرافيايي گرفته تا شي گرا.
- 1. 2. زيرسيستم هاي DSS
- زيرسيستم مديريت داده. شامل پايگاه داده و سيستم مديريت پايگاه داده است.
- زير سيستم مديريت مدل. بسته نرم افزاري است شامل مدلهاي کمي که قابليتهاي تحليلي سيستم را فراهم ميکنند. اين نرم افزار معمولا سيستم مديريت مبني بر مدل[8] (MBMS)ناميده مي شود.
- زيرسيستم دانش. براي پشتيباني از هر زيرسيستم ديگر به کار مي رود يا به عنوان يک مولفه مستقل عمل ميکند.
- سيستم رابط کاربر. براي ارتباط با کاربر و گرفتن دستورات از او به کار مي رود.
- کاربر هم به عنوان بخشي از سيستم درنظر گرفته مي شود.
- 2. سيستم خبره
نام سيستم خبره از اصطلاح سيستم خبره مبتني بر دانش مشتق شده است. سيستم خبره، سيستمي است که دانش بشري جمع آوري شده درون کامپيوتر را براي حل مسايلي که به طور معمول نياز به تخصص و مهارت بشر دارند، به کار ميبرد. چنين سيستم هايي مي توانند توسط افراد غير متخصص براي بهبود قابليتهاي حل مساله مورد استفاده قرار بگيرند. سيستم خبره همچنين مي تواند به عنوان دستيار مطلعي براي متخصصين به کار رود. سيستم هاي خبره براي نشر منابع کمياب دانش جهت نتايج بهتر و سازگار به کار مي روند.
- 2. 1. ساختار سيستم هاي خبره
سيستم هاي خبره از دو بخش اصلي تشکيل شده اند : محيط توسعه و محيط مشاوره (زمان اجرا). محيط توسعه توسط سازنده سيستم خبره براي ساخت مولفه ها و قراردادن دانش در پايگاه دانش به کار مي رود. محيط مشاوره توسط افراد غيرمتخصص براي کسب دانش خبره به کار مي رود.
سه مولفه اصلي که مجازا در هر سيستم خبره اي ديده مي شود، پايگاه دانش، موتور استنباط و رابط کاربر است. به طور کلي سيستم خبره مي تواند شامل مولفه هاي زير باشد :
- زيرسيستم کسب (فراگيري) دانش
جمع آوري، انتقال و تبديل مهارت حل مساله از مهارتها يا منابع دانشي مستند به يک برنامه کامپيوتري، براي ساخت يا توسعه پايگاه دانش. منابع بالقوه دانش شامل موارد زير است : مهارتهاي بشر، کتابها، اسناد چندرسانه اي، پايگاههاي داده، گزارشات تحقيقاتي و اطلاعات موجود در وب.
- پايگاه دانش
دربرگيرنده دانش مورد نياز براي درک، فرموله کردن و حل مساله مي باشد. شامل دو عنصر اصلي است: اول واقعيت ها شامل موقعيت مساله و تئوري حوزه مساله و توابع اکتشافي[9] خاص. دوم قوانين که استفاده از دانش را در جهت حل مساله خاص در دامنه ويژه هدايت مي کنند. دانش، نه فقط به معناي واقعيتهاي محض، ماده خام سيستم هاي خبره است. دانش درون پايگاه دانش، توسط پردازه اي به نام نمايشگر دانش، برنامه کامپيوتري را تشکيل مي دهد.
- موتور استنباط
مغز سيستم خبره است که نامهاي ديگري هم دارد مثل ساختار کنترلي و مفسر قانون. دراصل يک برنامه کامپيوتري است که روشي را براي استدلال درباره اطلاعات درون پايگاه دانش و براي فرموله کردن نتايچ فراهم مي کند.
- رابط کاربر
براي برقراري ارتباط موثر بين سيستم و کاربر، سيستم هاي خبره داراي يک پردازشگر زبان طبيعي مي باشند.
- تخته سياه ( محل کار)
بخشي از حافظه کاري است که براي توصيف مساله جاري که توسط ورودي مشخص مي گردد، تنظيم شده است. به علاوه براي ثبت نتايج نيز به کار مي رود.
- زيرسيستم توضيح ( توجيه کننده)
توانايي رديابي نتايج از منابع آنها، هم براي انتقال مهارتها و هم براي حل مساله مهم است. اين زيرسيستم مي تواند رفتار سيستم خبره را توسط پاسخ به پرسشهاي تعاملي توضيح دهد.
- سيستم تصفيه دانش
سيستمي که مي تواند دانش خود و کاربرد آن را تحليل کند، از آن فرابگيرد و براي مشاوره هاي بعدي آن را بهبود ببخشد[2].
- بهينه سازي در سيستم هاي رابطه اي
بهينه سازي در سيستم هاي رابطه اي هم به عنوان يک چالش و هم به عنوان يک فرصت مطرح مي گردد. چالش از آن جهت که هميشه براي رسيدن به کارايي قابل قبول در چنين سيستم هايي به بهينه سازي نيازمنديم و فرصت از آن جهت که اين مساله دقيقا يکي از نقاط قوت رويکرد رابطه اي است زيرا عبارات رابطه اي به اندازه کافي در سطح معنايي بالايي قرار دارند که بهينه سازي به بهترين نحو در آنها قابل اعمال باشد. در مقابل در سيستم هاي غير رابطه اي که درخواستها در سطح معنايي پايين تري مطرح مي گردد، بهينه سازي بايد توسط کاربر و به صورت دستي انجام گيرد. واقعيت اين است که بهينه ساز مي تواند بهتر از يک انسان عمل کند. در اين مورد دلايل زير وجود دارد :
- يک بهينه ساز خوب ثروت اطلاعاتي دارد که عمدتا در کاربران موجود نيست به ويژه که داراي اطلاعات آماري مشخصي مانند موارد زير است :
- تعداد مقادير در يک دامنه خاص
- تعداد تاپل فعلي در هر رابطه اصلي
- تعداد مقادير جداگانه جاري در هر صفت در هر رابطه پايه
- تعداد دفعاتي که هر يک از چنين مقاديري در هر صفت رخ مي دهد.
درنتيجه بهينه ساز قادر به ارزيابي دقيق تري از کارايي هر استراتژي براي پياده سازي درخواست خاص است و بنابراين با احتمال بيشتري، کاراترين پياده سازي را انتخاب مي کند.
- اگر آمار پايگاه در طول زمان تغيير کند، انتخاب استراتژي متفاوتي مطلوب خواهد بود. به بيان ديگر، به بهينهسازي مجدد نياز است. در سيستم رابطه اي بهينه سازي مجدد، ساده است ( اين کار شامل پردازش مجدد درخواست رابطه اي اوليه توسط بهينه ساز است ) ولي در سيستم غيررابطه اي اين کار مستلزم دوباره نويسي برنامه است.
- بهينه ساز يک برنامه است و بنابراين طبق تعريف صبورتر از يک کاربر نوعي است. بهينه ساز کاملا قادر است صدها استراتژي پياده سازي مختلف را براي يک درخواست درنظر بگيرد درحاليکه يک کاربر بيشتر از سه يا چهار استراتژي را درنظر نمي گيرد.
- بهينه ساز مي تواند به عنوان تجسمي از مهارتها و خدمات “بهترين” افراد برنامه نويس درنظرگرفته شود. درنتيجه تاثير آن خدمات و مهارتها دراختيار همه افراد قرار مي گيرد.
بنابراين هدف بهينه ساز، انتخاب يک استراتژي براي ارزيابي عبارت رابطه اي داده شده است.
- 1. مروري بر پردازش پرس و جو
4 مرحله اصلي در پردازش پرس و جو وجود دارد :
- قالب ريزي پرس و جو به شکل داخلي (تبديل پرس و جو اصلي به نمايش دروني که براي عمليات ماشين مناسبتر است. مانند درخت نحو مجرد و درخت پرس و جو)
- تبديل به شکل متعارف (بهينه ساز، بدون درنظر گرفتن مقادير داده واقعي و مسيرهاي دستيابي فيزيکي موجود در پايگاه داده، بهينه سازي هايي انجام مي دهد يعني تبديل نمايش دروني به شکل معادل با کارايي بيشتر)
- انتخاب رويه هاي سطح پايين کانديد (کار اصلي آن درنظرگرفتن پرس و جو به عنوان مجموعه اي از عمليات سطح پايين است. براي هر عمليات سطح پايين چندين رويه پياده سازي درنظرگرفته شده است و براي هر رويه فرمول هزينه متناظر با آن تعريف مي شود. معمولا برحسب I/O ديسک يا بهره وري CPU)
- توليد طرحهاي پرس و جو و انتخاب ارزان ترين طرح (هر ترکيب مجموعه اي از رويه هاي پياده سازي کانديد ساخته مي شود به نحوي که هر عمليات توسط يک رويه پياده سازي مي شود)
- 2. بهينه سازي پرس و جو
بهينه سازي پرس و جو، فرايند انتخاب کاراترين طرح ارزيابي پرس و جو از ميان استراتژي هاي بسياري است که اغلب براي پردازش يک پرس و جو ممکن است، مخصوصا براي مواردي که پرس و جو پيچيده باشد.
يک جنبه از بهينه سازي در سطح جبر رابطه اي رخ مي دهد که در آن سيستم تلاش مي کند عبارتي بيابد که معادل با عبارت داده شده ولي براي اجرا کاراتر باشد. جنبه ديگر انتخاب يک استراتژي جزئي براي پردازش است مثل انتخاب الگوريتم مورد استفاده براي اجراي عمليات، انديس خاص و….
کار بهينه ساز پرس و جو اين است که يک طرح براي ارزيابي پرس و جو ارائه کند که همان نتايج پرس و جوي اوليه را با کمترين هزينه ممکن (و يا حداقل با اختلاف هزينه کم نسبت به کمترين هزينه ممکن) ايجاد کند.
براي انتخاب از ميان طرحهاي ارزيابي پرس و جوي متفاوت، بهينه ساز بايد هزينه طرحها را تخمين بزند زيرا محاسبه هزينه دقيق ارزيابي يک طرح معمولا بدون ارزيابي واقعي آن ممکن نيست. در عوض بهينه ساز با استفاده از اطلاعات آماري در مورد روابط (مانند اندازه رابطه و عمق انديس ها) تخمين خوبي از هزينه طرح ارائه مي کند و عمدتا ميزان دستيابي به ديسک هزينه پردازش را تعيين مي کند.
توليد طرحهاي ارزيابي پرس و جو شامل دو مرحله است که به صورت تو درتو اجرا مي شوند :
- توليد عبارات معادل
- تفسير عبارات حاصل به روشهاي ديگر براي توليد طرحهاي ارزيابي پرس و جوي ديگر
از آنجا که به روزرساني آمار پايگاه داده سربار زيادي ايجاد مي کند اغلب سيستم ها چنين کاري را درطول دوره هايي که بار سيستم کم است انجام مي دهند. بنابراين چنين آمارهايي کاملا صحيح نيستند.
براي بهبود دقت تخمين طرحهاي ارزيابي، اغلب بهينه سازها اطلاعات آماري زيادي نگهداري مي کنند براي اين کار بعضي پايگاه داده ها، توزيع مقادير هر صفت را به صورت نمودار ميله اي[10] نگهداري مي کنند که در آن مقادير بين محدودههاي مختلف، تقسيم مي شوند و نمودار ميله اي به هر محدوده تعداد تاپلي که مقادير اين صفت آنها در اين محدوده قرار مي گيرد، متناظر مي کند. مثلا براي توزيع يکنواخت مقادير ( هر مقدار با احتمال مساوي آمده باشد )، تعداد تاپل هاي تخميني عمليات انتخاب براساس مقدار يک فيلد خاص، با تعداد کل تاپلها تقسيم بر تعداد مقادير جداگانه ظاهر شده در رابطه براي يک خصوصيت خاص است.
دو عبارت جبر رابطه اي معادل گفته مي شوند اگر روي هر نمونه پايگه داده معتبر هر دو عبارت مجموعه تاپلهاي يکساين توليد کنند و يک قانون هم ارزي مي گويد که دو عبارت با شکل ظاهري متفاوت، معادلند.
مثال : عمليات انتخاب عطفي، مي تواند به دنباله اي از انتخاب هاي تکي تبديل شود يا تنها آخرين عمليات در دنباله عمليات تصوير[11] مورد نياز است.
نحوه عمل بهينه ساز پرس و جو با استفاده از قوانين هم ارزي به اين شکل است که با داشتن يک عبارت، اگر يک زيرعبارت بهينه سازي با طرف اول قانون هم ارزي مطابقت داشته باشد، بهينه ساز آن بخش را با زيرعبارت طرف دوم از قانون هم ارزي جايگزين مي کند و اين کار را آنقدر ادامه مي دهد تا ديگر انطباقي در قوانين رخ ندهد و عبارت جديدي توليد نشود. مشکل اين روش آن است که هم از لحاظ فضا و هم زمان، هزينه بر است.
هميشه لازم نيست که هر عبارتي را که مي توانيم با استفاده از قوانين هم ارزي توليد کنيم. تکنيک هايي که اجازه ميدهند دو عبارت معادل به يک زيرعبارت مشترک اشاره کنند، نيازهاي حافظه را تا حد زيادي کاهش مي دهند.
در ارتباط با انتخاب بهترين طرح ارزيابي، دو رويکرد وجود دارد :
- کل طرحها را جستجو مي کند و با توجه به هزينه، بهترين طرح را انتخاب مي کند
- دومين رويکرد از توابع اکتشافي براي انتخاب استفاده مي کند
اغلب بهينه سازهاي عملياتي ترکيبي از اين دو رويکرد را به کار مي برند. به عنوان مثالي از قانون اکتشافي مي توان گفت عمليات انتخاب را تا حد ممکن زودتر انجام بده[3,4].
- جستجو
روشهاي جستجو هنوز در مرکز اهميت مسايل هوش مصنوعي قرار دارند، نه تنها به اين دليل که اغلب سيستمها براساس آنها ساخته شده اند بلکه به دليل آنکه از طريق درک الگوريتم هاي جستجوست که مي توان پيشبيني کرد چه مسايلي در هوش مصنوعي قابل حل است. يک روش جستجوي خوب نوعا بعضي اطلاعات خاص در مورد مساله يا دانش کلي را براي تمرکز جستجو روي نواحيي از فضاي جستجو که شانس بيشتري براي وجود راه حل دارند، به کار ميبرند.
- 1. روشهاي جستجوي ساخت يافته[12]
همان طور که مي دانيد استراتژي هاي جستجوي ساختار نيافته[13]، مي توانند از طريق توليد سيستماتيک وضعيت هاي جديد و مقايسه آنها با هدف، راه حل مسايل را بيابند. متاسفانه اين استراتژي ها در بيشتر موارد، ناکارا هستند ولي استراتژي جستجوي ساختيافته که از دانش خاص مساله استفاده ميکند، مي تواند راه حل هاي کارآمدتري ارائه کند.
- 1. 1. جستجوي اول بهترين
اگر مي توانستيم واقعا بهترين گره را گسترش دهيم، پس اصلا جستجويي انجام نداده ايم. آنچه ما مي توانيم انجام دهيم، انتخاب گره اي است که براساس تابع ارزيابي، بهترين انتخاب به نظر مي رسد. درواقع، گاهي تابع ارزيابي مي تواند منجر به گمراه شدن جستجو شود. هدف از روشهاي اول بهترين يافتن کم هزينه ترين راه حل است. براي تمرکز بر جستجو، معيار هزينه بايد تخمين هايي از هزينه مسير از يک حالت به نزديک ترين حالت هدف باشد. ما دو رويکرد اصلي را درنظر مي گيريم. اولي نزديک ترين گره به هدف و دومي گره روي کم هزينه ترين مسير را گسترش مي دهد.
- 1. 1. 1. کمينه کردن هزينه تخميني براي رسيدن به يک هدف : جستجوي حريصانه
اين روش هزينه تخميني براي رسيدن به هدف را کمينه مي کند که يکي از ساده ترين روشهاي جستجوي اول-بهترين است. يعني اول گره اي گسترش مي يابد که به نظرمي رسد نزديک ترين وضعيت به گره هدف را دارد. براي ارزيابي اين هزينه از تابع اکتشافي استفاده مي کنيم. چنين جستجويي، جستجوي حريصانه ناميده مي شود. تابع اکتشافي براي مساله خاص طراحي مي گردد. جستجوي حريصانه منجر به شروعهاي غلط و گسترش گره هاي غير ضروري مي گردد. به علاوه اگر مراقب گره هاي تکراري نباشيم ممکن است هرگز راه حلي پيدا نکنيم.
جستجوي حريصانه از لحاظ دنبال کردن يک مسير واحد به سمت هدف شبيه روش اول-عمق است ولي اگر به يک پايان مرده برسد، به سطح بالاتر برمي گردد. اين جستجو بهينه و کامل نيست چون مي تواند مسير بي پاياني را دنبال کند و هيچ گاه ساير احتمالات را بررسي نکند. وقتي حداکثر عمق فضاي جستجو، m باشد، بدترين پيچيدگي زماني آن O(bm) خواهد بود.(b حداکثر تعداد فرزندان يک گره مي باشد) و از آنجا که کليه گره ها در حافظه نگهداري مي شوند، پيچيدگي فضايي آن مشابه پيچيدگي زماني خواهد بود. با استفاده از يک تابع اکتشافي مناسب (بسته به مساله و کيفيت تابع اکتشافي)، پيچيدگي فضايي و زماني تا حد زيادي کاهش مي يابد.
[1] Optimization
5 Non-Linear Programming (NLP)
[6] Decision Support System
[7] Online
[8] Model-based Management System
[9] Heuristic function
[10] Histogram
[11] Projection
[12] Informed
[13] Uninformed
نقد و بررسیها
هنوز بررسیای ثبت نشده است.