صفحه 1:
الگوریتم هاي جستجوي آگاهانه
تهیه کننده: عبدالرضا ميرزابي
صفحه 2:
سرفصل مطالب
آلا جستجوي اولبهترین
Ml جستجوي حریصانه
جستجوي “A
#ا جسحجوى 4A حافظله محدوه
لا جستجوي عمیق کننده تكراري ۸
آلا جستجوي اول بهترین بازگشتی(۳۸۵ 88
۳ 251/۸
Ml هيوربستيك ها
الگوریتم هاي جستجوي محلي
لا جستجوي 20062۱9 0عاهابامزو
Hl الگوریتم هاي ژنتيك
لا جستجوي online
2 هي تنج
كامبيوتر
صفحه 3:
مروز جستجوى درجت
function GENERAL-SEARCH( problem, strategy) returns a solution , or failure
initialize the search tree using the initial state of problem
loop do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according to sérategy
if the node contains the goal state then return the corresponding solution
else expand the node and add the resulting node to the search tree
end
* استراتژي توسط ترتیب گسترش یافتن گره ها تعریف مي شود.
صفحه 4:
تختتتقوی اول رین
نمونه اي از i عمومي graph-search | tree-search
است که در ان یک گره بر آساس یک تابع ارزيابي (00)] براي گسترش
انتخاب می شود.
* تابع ارزيابي evaluation function تخمین "میزان مطلوب بودن " گره
* هربار مطلوب ترین گره گسترش نيافته را بسط مي دهد.
۳ پیاده سازی:
* گره ها در a fringe ترتیب نزولي میزان مطلوبیت مرتب مي شوند.
* يك صف اولويت
* حالت هاي خاص
جستجوي حریصانه 56۲۳6 6۲660
* جستجوي ۵«
ea 4 تون من وق زیر
صفحه 5:
جستجوي اول بهترین حریصانه
1 تبع هيوريستيك (0
gies Rape” مسیر از گره 9 تا نزدیکترین گره هدف
* براي مثال. در نة نقشه روماني مي توان مسیر از هر شهري به
بخارست را از طریق مسافت يك خط مستقیم از آن شهر به بخارست
SF geass
Ne p(N) ف اضله مستقیماز 9 تاب خارست
جستجوي اول -بهترين حريصانه
* جستجوي حريصانه كره اي را كسترش مي دهد كه به نظر مي رسد
نزديكترين كره به هدف ( بخارست) باشد.
* تابع ارزيابي (8)0 -(1)0
صتعتي اصفهان دانشکد
صفحه 6:
نقشه رومانی به همراه هزینه مراحل برحسب ۱۲۰
‘Straight-line distance
ا
0. سوه ‘Bucharest
Arad مهد
Bocharest 0
Craiova
Dobreta
Eforie
Fagaras 176
Ginrgin 7
vast Blirsowa Ist
26
24
اب
بح
300
مور 30,
193
as 253
‘Timisoara ود
م تا
مروت Vashi ها
Zerind 274
صفحه 7:
جستجوي اول -بهترین حربصانه
صفحه 8:
تسحجوق اول «بيعرين حويصانة
aD هع
32 we
صفحه 9:
Male Ae, al eee
كد .
صفحه 10:
جستجوي اول بهترین حریصانه
D> =D
ED هه G> =>
Sb DP-Gichaes
252
صفحه 11:
خواص جستجوي اول -بهترین حریصانه
* کال
-خیر (ممکن است در حلقه بینهایت گیر کند)
پيچيدگي زماني؟
(0)8 -لمابا ی کهیوریستیکخوبم یت ولند به شدتب هود یابد
* پیچیدگی حافطه؟
La oF plas O(b™) - را در حافظه نگه می دارد.
بهینه؟
- خیر (مثلا در مثال قبل مسیر بهینه اي وجود دارد که از دید
جستجوي حریصانه مخفي مي ماند).
lye gute 11 دنک
صفحه 12:
حلقه بینهایت در جستجوي حریصانه
‘Straight-line distance
Bucharest
Arad معد
Bucharest 6
Craiova
para
253
30
و
374
Neamt [) ن أكقا ن] غمصقعلة [] أ5ها
12
كامبيوتر
صفحه 13:
A جستجوي
* ایده: از گسترش مسيرهايي که تاکنون مشخص شده پرهزینه
م باشس» جاب كن.
* تابع ارزيابي
صفحه 14:
صفحه 15:
صفحه 16:
صفحه 17:
صفحه 18:
سیب
صفحه 19:
صفحه 20:
هيوربستيك قابل قبول
* يك هيوريستيك (0)0 قابل قبول است اگر براي هر گره 0 داشته باشیم :
*؟ A(n) s h’(n)
* که (۲0/ هزینه واقعي براي رسیدن به هدف از گره 0] مي باشد.
* يك هيوريستيك قابل قبول هرگز هزینه رسیدن به هدف را بیش از حد
تخمین نمي زند. يعني خوش بینانه است.
* مثال: هيوريستيك(0)م,و0ا هیچگاه فاصله را بیش از حد واقعي تخمین
نمي زند.
* ثضبه: اگر (0)0 قابل قبول باشد. ۵* با استفاده از ۲8۴6-5۴6۸86۷
بهینه است
20
صفحه 21:
اثبات بهينگي "A
* فرض کنید يك جواب زیر بهینه مانند و5) ایجاد شده و در ۲۲۱096 قرار
دارد. همچنین فرض کنید 9 يك گره گسترش نیافته روي کوتاهترین
Start
مسير به هدف بهینه ) باشد. 3
ce ۱ 9
f(G,) = g(G,) since A(G,) = 0
g(G,) > g(G) since G, is suboptimal
f(G) = 9(G) since A(G) = 0
f(G,) > f(G) from above
21
صفحه 22:
۳ ۰
اثبات بهینگی ۸
فا ۳
* فرض كنيد يك جواب زير بهینه مانند وق) ایجاد شده و در ۲1096 قرار
دارد. همچنین فرض کنید 9 يك گره گسترش نیافته روي کوتاهترین
6 مسير به هدف بهینه ) باشد.
© OG,
f(G,) > f(G) from above
h(n) << h*(n) since h is admissible
g(n) + h(n) = g(n) + h(n)
f(n) = f(G)
چون (۲)۳ < (و6))؟ است ۰۸ هیچگاه رت را براي گسترش انتخاب نمي کند
22
انشکده
دانشگاه صنمتي اء و كامييوتر
صفحه 23:
* اگر به جای1865-56۸861 از 68۵۳۳-5۲۵86 استفاده کنیم. آنگاه
* ممکن است راه حلهای نیمه بهینه برگردانده شوند. زیرا -68۵۲
58۸06 می تواند میسر بهینه به يك حالت تکراری را کنار بگذارده اگز
اولین گره توليدي نباشد.
* دو راهكار براي حل اين مشكل:
* اولین راه حل, این است که 68۵۴۳۱5۳۸86۱ را به نحوي توسعه بدهيم که
از بین مسيري که به يك گره مي رسد آن مسيري که پرهزینه تر است را کنار
بگذارد. این روش فضاي زيادي آشغال مي کند. اما بهينگي را تضمین مي کند.
راه حل دوم. اطمینان از این موضوع است که مسیر بهینه به هر حالت تكراري»
هميشه اولین مسيري است که دنبال مي شود. شرط سازگاري (يا يکنواختي)
23
دانشگاه صنعتي اسف
كامبيوتر
صفحه 24:
See ۱ هاي سازگار
* يك هيوريستيك سازگار ونم است اگر
(0 + (9(ق) >(
۶ شكلي از قانون كلي نامساوي مثلث است که تصریح مي کند هیچ
ضلعي از يك مثلث نمي تواند بلندتر از مجموع دو ضلع دیگر باشد.
* هر هيوريستيك سازگا قابل قبول نیز هست.
* تضبه: اگر (۱)۳ سازكار باشد. 8* با استفاده از 8011 مع 1-5]ط م08
امك
دانشگاه صتعتي اصفهان دانشکده بر و کر
صفحه 25:
هیوربستیک هاي سازگار
كاه (0)] در طول هر مسيريء غيرنزولي است.
كط + )د د رمم
Fas) + ola’) h(t) nr)
* اگر (0) سازگار باشد
(۲ + (و <
= F(a)
ان نتیجه گرفت که رشته اي از ی ل 8
كسترش يافته اند به ترتيب غيرنزولي (1)0 مي 68/681- SEARCH
باشد.
* در نتيجه. اولين كره هدفي كه براي كسترش انتخاب مي شود بايد يك راه
حل بهينه باشد. زيرا تمامى كره هاي بعدي حداقل به همان اندازه هزينة
وخواهند داشت.
دانشگاه صتعتي اصفهان دانشکده
صفحه 26:
صفحه 27:
5 . *
* اولین راه حل پیداشده باید يك راه حل بهينه باشد
* زیرا گره های هدف در تمامی ۲لا00010هاي cae داراي هزینه ؟
بيشتري خواهند بود و در نتیجه هزينة ت) بالاتري نیز دارند (زیرا
cle oF oli هدف داراي ۱)0(<0] هستند).
* جستجوی ۵۸* کامل است.
* همان طور که نوارهاي با ۴ در حال افزایش را اضافه می کنیم. باید
بالاخره به نواري برسیم که در آنجا ] مساوي هزينة مسیر تا يك
حالت هدف است.
27
صفحه 28:
“A 5 | ۰
oie
-بله. مگر اينکه تعدادی نامحدود گره با (۴)63 > ۴ وجود داشته باشد.
*A در گراف هاي متناهی محلی ( با فاکتور انشعاب محدود) AIS
مى باشد : ي
پيچيدگي زماني؟
= نمايي
Wi Fis ©
- نمايي تمام گره ها را در حافظه نگه مي دارد.
صفحه 29:
“A 5 les
بهينه؟ *
بله نمی تواند وبر] را گسترش دهد مگر آنکه ] تمام شده باشد. -
تمام گرم ها با > (۲)۳* را گسترشمیدهد. 7*۸
برخيگره ها با 2 (۲0* را گسترشميدهد. 7 ۸
هرگز گره لیب ا]< (200* را گسترش ن ميدهد. - ۸
دارليكارلييهینه 65۳61606 00۲1۳0۵۷۱ مي_اشد *۵ *
يعني هیچ الگوریتم بهينة ديگري تضمین نمي کند که تعداد گره هايي *
گسترش می دهد از ۸۵* کمتر باشد.
* علت این امر آن است که هر الگوریتمی که تمامی گره ها را با > (۴)۳* را
گسترش ندهد خطر از دست دادن راه حل بهینه را دارد.
29
صفحه 30:
جستجوی ۸" با حافظه محدود
* زمان محاسبه نقطه ضعف اصلی ۵" نیست.
gals aay Sil saliasieal gh کووهای لد هدر خافطظه
نگهداري مي کند معمولا بسیار بیشتر از آنکه وقت کم بیاورد.
حافظه کم می آورد.
* در مورد بسياري از مسائل بزرگ, عملي نيست.
* چند راه حل برای مسأله حافظه در ۸۵
* جستجوي عمیق کننده تكراري AX (IDA*)
* جستجوي اولبهترین بازگشتي(88۴5)
7 جستجوي (ساده شده) *A با حافظه محدود («6شظل
30
كامبيوتر
صفحه 31:
‘IDA
ايدة استفاده از راهكار عميق كننده تكراري در زمينة جستجوي *
آكاهانه
*IDA تفاوت اصلي بین 25| و *
محدوده عمقی از محدوده ؟ (یعنی +9) استفاده we 4 AIDA در *
مي شود.
سر هر تگرا سار بر یی شمرین ریما سیر ماه *
هايي است که از برش تکرار قبلي بیشتر باشند.
31
صفحه 32:
جستجوي اول -بهترین بازگشتي (۴8۴5)
* يك الگوریتم بازگشتي با فضاي خطي که سعي مي کند از جستجوي
اول- بهترین استاندارد تقلید کند.
ساختار ٩58۳5 مشابه جستجوی اول عمق باز است. اما به جای
ادامه دادن مسیر فعلي به طور نامشخص, خود را از مقدار بهترین ؟ مسیر
جایگزین قابل دسترس از تمام اجداد گره فعلي مطلع نگه می دارد.
اگر گره فعلي از این محدوده فراتر رود. تابع بازگشت
برمي گرداند تا روي يك مسیر جایگزین دیگر قرار گیرد.
در بازگشت به عقب مقدار مربوط به هر گره موجود در مسیر را با
بهترین مقدار ] فرزندانش جایگزین مي کند.
بتابراين رن مجددرآتیچه فعلي هون مفعکن هي بان
32
آن را به عقب
دانشگاه صتعتي اصفهان دانشکده برق و کامپپوتر
صفحه 33:
جستجوي اول -بهترين بازكشتي (RBFS)
function RECURSIVE-BEST-FIRST-SEARCH(prob/eui) return a solution or failure
return RFBS(problemMAKE-NODE(INITIAL-STATE[problen]).0)
function RFBS( problem, node, f limit return a sobtion or failure and a new
if GOAL-TEST[probleai(STATE[zode)) then return uode
successors EXPAND(siode, problem)
if successorsis empty then retwn failure, ©
for each sin successors do
۶] > دقع )حمس + INS), Muode))
repeat
best — the lowest £value node in successors
if f[best| > £ Limit then return failure, لعف
alremative — the second lowest fvalue among successors
result, f[bes — RBFS(problem, best, min(f limit, altemative))
if result = failure then return ار
33 دانشگاه
صفحه 34:
جستجوي اول -بهترين بازكشتي (11815)
۱۱۳ Zerind
447 449
Arad Fagaras Oradea
646 415 526
Craiova Pitesti Sibiu
34 دانشگاه
صفحه 35:
, جستجوي اول بهترین بازگشتي (RBFS)
Zerind
Arad
646
Sibiu Bucharest
591 450
35
صفحه 36:
$53
Craiova
65
Arad Fagaras Oradea
646 450 526
Craiova
526
nichares}
418
اه صتعتي اصفهان دانشکده برق و کامپپوتر
صفحه 37:
“IDAs sis .SRBFS * ميباشد
- هنوز ک ترش اضافي گره ها وجود دارد( تغییر عقیده)
fae hast 2
55 يدگي زماني آن نسبتاً شک است: هم به دقت تابع هيوريستيك بستگي
دارد وهم به آين كه در حين كسترش ره هاء بهترين مسير هر جند وقت يكبار
تغيير مى کند.
- مانند 08]|* در معرض افزايش نمايي بيجيدكي زماني قرار دارد
* پیچیدگی حافظه؟
O(bd) -
بهینه؟
- همانند ۰*۸۵ الگوریتم 88۳5 نیز يك الگوریتم بهینه است اگر تابع هيوريستيك 1١
قابل قبول باشد.
37
صفحه 38:
غواض جستجري 8815
۰ 88۴6و ۱0۸+ هرد
* ممکن است در معرض افزایش نمايي بالقوه در پيچيدگي همراه با
جستجو در گرافها قرار بگیرند. .
* آنها نمي توانند حالتهاي تكراري. به جز آنهايي را که بر روي مسیر فعلي
قرار دارند بررسي کنند. در نتیجه. ممکن است يك حالت را چندین بار
اکتشاف کنند.
از میزان بسیار کم حافظه Dey
scl, bi SIDA * را نكهداريميكند (محدوديتمقدار فعلي))
* 8۳5 لطاهاتتب یشتریا در حافظه نكهداييميكد ولوفقطاز O(bd)
حافظه لستفادم میک ند. mo ۱
38
توانند از آن استفاده
صفحه 39:
*Memory Bounded A (Simplified)
]لس استفاده از تمامي حافظه موجود ۱
7 يعني, گسترش بهترین گره هاي برگي تا زماني که حافظه موجود پر
شود.
* ۸ دقیقامنل۸* عملمیکنده یعنیتا نمانیکه حافظه
پر شود. بسهترینگره را گسترشميدهد.
۱ در صورت پر شدن حافظه هميشه بدترین گره برگي (گرهي با
بیشترین مقدار ۴) را از حافظه حذف می کند
* اطلاعات گره هاي فراموش شده را در پدرشان ذخیره مي کند
39
صفحه 40:
*Memory Bounded A (Simplified)
“SMA *
* کامل است. اگر راه حل دست يافتني وجود داشته باشد (يعني اگر
عمق کم عمقترین گره هدف کمتر از اندازة حافظه باشد).
* این الگوریتم بهینه است در صورتي که راه حل بهينة دست يافتني
وجود داشته باشد. در غیر این صورت بهترین راه حل دستيافتني را
برمي گرداند. ۱
40
صفحه 41:
هيوريستيك هاي قابل قبول
* مثال براي پازل 8 تايي:
۰ تعداد کاشيهاييکه در جايشود قرار ن_گرفته لند.
hy مجموع ف ولصلفقيو عموديکاشیها از موقعيتهايهدفشان(ف اصله
janhattan L, city block
5 5 2 1
هر دو قابل قبول
5 4 3
8 7 6
8 > (كايط
و + 2ج 2ع 1ع وه رقي
41
صفحه 42:
اگر بازاء هر ۱ داشته باشیم (/, = (2)0/(و هر دو
هيوريستيك قابل قبول باشند) آنگاه 2 بر 1( تسلط دارد و براي
* مثال هزینه جستجو: تعداد گره های تولید شده در عمق های مختلف:
۱ 0212 *
IDS = 3,644,035 nodes
A‘(h,) = 227 nodes
A‘(h,) = 73 nodes
d=24 *
IDS = too many nodes
A‘(h,) = 39,135 nodes
A‘(h,) = 1,641 nodes
42
صفحه 43:
ضریب انشعاب موثر 0"
ضریب انشعاب موثر:(5۳ع)
اگر تعداد گره هاي گسترش يافته توسط روال جستجو لا و عمق راه حل 0 باشد
0 به صورت زیر محاسبه مي شود:
)+ ... +(#ی) + 1+0 ع ۸+1
مثال: اگر ۸۵* راه حلي را در عم 5 با استفاده از 52 گره پیدا کند. ضریب
انشعاب موثر؟
53 = 1+ b* + (b*)? +...(b*)>
b* = 1.92
در يك هيوريستيك هر چه فاکتور انشعاب به يك نزدیکتر باشد. بهتر است *
آن هيوريستيك کیفیت کشف کنندگي بيشتري دارد.
43
كامبيوتر
صفحه 44:
رابطه بین هزینه جستجو و ضریب انشعاب موثر
At(h)
179
44
(A)
179
148
148
1.48
Effective Branching Factor
Ips
2.45
28
وله
Search Cost
At)
صفحه 45:
ابداع توابع هيوريستيك
* مسأله اي که تعداد کمتري محدودیت براي اقدامات دارد. يك
مسألةتعدیل شده ۲61260 ناميده مى
* هزينة يك راه حل بهینه براي يك مسألة تعدیل شده؛ يك هیوریستیک
قابل قبول براي مسأّلة اصلی است.
هزینه راه حل بهینه يك مسأله تعديل شده. بیشتر از هزینه راه حل
بهینه در مسأله واقعي نیست.
* مثال: پازل 8 تایی. يك کاشی می تواند از خانه ۸ به خانه 8 برود اگر ۸
مجاور 8 باشد و 8 خالی باشد. -
45
صفحه 46:
ابداع توابع هيوريستيك
* مثال: پازل 8 تايي. يك كاشي مي تواند از خانه ۸ به خانه 8 برود اگر ۸۸
مجاور 8 باشد و خالي باشد. ميتوانیم با خذف يك پا هر دو شرط سه
مسألة تفترای حتاف تولید ied
* يك كاشى مى تواند از خانه a A خانه 8 برود اگر ۵ مجاور 8 باشد. (A)
* يك كاشى مى تواند از خانه 8 به خانه 8 برود اكر 8 خالى باشد.
* يك كاشى مى تواند از خانه 8 به خانه 8 برود. )52( -
46
صفحه 47:
الگوریتم هاي حستجوي محلي و مسائل بهینه سازي
در بسياري از مسائل بهینه سازي» مسیر راه حل اهمیت ندارد؛
خود خالت هدف پاسخ مسأله می باشد.
* فضاي حالت - مجموعه پیکره بندي هاي کامل
5 هدف - يافتن يك ييكره بندي كه محدوديت هاي مسأله را ارضاء
کند. مانند مساله 0- وزير
* در چنین مواردي مي توان از الگوریتم هاي جستجوي محلي
بهره گرفت.
* يك حالت "فعلي ” را به تنهايي در نظر بگیر؛ سعي کن آن را sete
47
صفحه 48:
الگوریتم هاي حستجوي محلي و مسائل بهینه سازي
* جستجوي محلي - استفاده از يك حالت فعلي و حرکت به
حالت هاي همسایه
* مزایا:
- استفاده از حافظه بسیار کم
7 یافتن راه حل هاي معقول در اغلب موارد در فضاهاي حالت بزرگ و
یا نامحدود
* مفید براي مسائل بهینه سازي محض
< یافتن بهترین حالت بر طبق تابع هدف (objective function)
48
صفحه 49:
State space landscape |
* يك 130056306 هم شامل "محل" (كه توسط حالت تعريف مي شود) و
هم شامل "ارتفاع" (كه توسط مقدار تابع هيوريستيك هزينه يا تابع هدف
تعريف مي شود) مي باشد.
° اكر ارتفاع متناظر هزينه باشدء آنكاه هدف يافتن عميقترين دره (يك
کمينة سراسري) است و اگر ارتفاع متناظر با تابع هدف باشد. آنگاه هدف
یافتن بلندترین قله (يك بيشينة سراسري) است.
* يك الگوریتم جستجوي محلي کامل. هدف را (در صورت وجود) پیدا مي
کند lial palette! cao ely gs gel dh
49
كامبيوتر
صفحه 50:
State space landscape
objective function Bisbal maxis
local maxinmm
“flat” local maximmm
cunent
state
Forel yp oS lye gate ts 50
صفحه 51:
تيه نوردي( يا كراديان صعودي /نزولي)
* الكوريتم جستجوي تيه نوردي فقط از يك حلقه تشكيز مي شود كه
مدام در جهت افزايش مقدار حركت مي كند (يعني به سمت بالاي تيه).
* الگوریتم هنگامي خانمه پیدا مي کند که به قلّه اي برسد که در آنا
هیچ همسایه اي مقدار بيشتري نداشته باشد.
۶ این الگوریتم. درخت جستجو را نگهداري نمي کند. بنابراین» ساختمان
دادة گره فعلي تنها نیاز به ثبت حالت و مقدار تابع هدفش را دارد.
تيه نوردی. فراتر از همسایه های مجاور حالت فعلی را نگاه نمی کند.
51
صفحه 52:
تبه نوردي( با گرادیان صعودي انزولي)
52
function عتما د ماع (ماامم )نت11۲ that is a local maximum
inputs: probiers, a problem
local variables: current, a node
neighbor, a node
current — Maxe-Nove(Inrtan-Stare|probleri))
loop do
neighbor +a highest-valued successor of current
if Varcr|neighbor] < Vatunfeurrent] then return StatE[currend]
current — neighbor
صفحه 53:
مثال: 19-وزير
١ وزیر را در یكصفحه شطرنج!۲ * N به كونهلوقرار بدم
که هیچ دو وزیریدر یكسطر ستونو یاقطر قرار نگيرند.
8- وزیر:
* فرمول بندي حالت کامل: هر حالت شامل 8 وزیر يعني يکي در هر ستون
* تابع پسین همه حالتهاي ممكني که با جابجايي یک وزیر به مربع ديگري در
همان ستون تولید مي شود را برمي گرداند. هر حالت 7*8 پسین دارد
* تابع هيوريستيك!] تعداد جفتهايي از وزبرهاست که چه به صورت مستقیم و
چه غیر مستقیم در حال حمله به یکدیگر هستند.
* كمينة سراسري این تابع صفر است که فقط در راه حل کامل اتفاق مي افتد.
53
صفحه 54:
بهترین پسین داراي ۱212 است.
1111 1 1 1 54
صفحه 55:
۴ تبه نوردي اغلب به دلايل زير كير مي كند:
* بیشینه هاي محلي: الگوريتمهاي تپه نوردي که به همسايگي يك
محلي مي ر ندء رو به بالا به ت قله شیده مي شوند.
ولي بس از أن كير مي كنند و جاي ديگري نمي روند.
Ridge * دارلييكيشته بيشينة محليهستد كه كذشتراز لنها
ب ولا گوریتمهايحریصب سیر مشکللیست
* فلاتها: فلات ناحیه اي از دورنماي فضاي حالت است که در آن تابع
اززیاب: ثابت cal فلات مى توائد محلی مسطح باشد که
از آن هیچ مسیر رو به بالايي وجود ندارد یا يك شانه باشد که از آن
بتوان به بالاتر هم رفت.
55
صفحه 56:
انواع ديكر تيه نوردي
* تپه نوردي انفاقي stochastic hill climbing
* به صورت تصادفي از میان حركتهاي رو به بالا يكي را انتخاب مي
کند.
* احتمال این انتخاب مي تواند براساس شیب حركتهاي رو به بالا تغییر
کند.
* اين روش معمولا کندتر از تیزترین شیب به نتیجه مي رسد. اما در
بعضی از ۱30056306 هاي حالت. بهترین راه حل را پیدا می کند.
57
صفحه 57:
انواع ديكر تبه نوردي
* تیه نوردی first choice hill climbing «is 5° al
* تبه نوردي اتفاقي را به كار مي كيرد به اين صورت كه به صورت
تصادفي يسين توليد مي كند تا زماني كه يسيني توليد شود كه از
حالت فعلي بهتر باشد. این راهبرد هنگامي مناسب است که يك حالت
داراي تعداد زيادي (مثلاً هزار) پسین باشد.
* تیه نوردی با شروع مجدد تصادفي ۲۱ ۲65۱۵۲۲ ۲3۲00۳0
climbing
* يك مجموعه جستجوي تپه نوردي را از حالتهاي شروع تصادفي اجرا مي
کند و هنگامي که يك هدف پیدا شد متوقف ميشود. این روش با
احتمال نزديك به يك. کامل مي باشد.
58
صفحه 58:
سردسازي شبیه سازي شده
التوريتم نبه نوردي كه هركز حركت رو به پایین به سمت حالتهايي با
مقادیر کمتر (با هزينة بالاتر) را انجام نمی دهد. ناکامل بودنش قطعي
است. زیرا ممکن است در يك بيشينة محلي گیر کند.
* در مقابل» يك راهييمابي كاملا تصادفي walk 800000( يعني حركت به
پسيني که از مجموعة gas, به طور يكتواعت و كاملة تصادفي انتخاب
شده است) کامل ولي به شدت ناكا رآمد مي باشد.
در نتيجهء تلاش در جهت تركيب تيه نوردي با يك راهييماي بي تصادفي
که هم کارآمد و هم کامل باشد. کار معقولي به نظر مي رسد.
سردسازي شبیه سازي شده. يك چنین الگوريتمي است.
59
صفحه 59:
سردسازي شبیه سازي شده
Simulated Annealing :ow! *
۲ 9 مات ۶
. از ماكزيمم هاي محلي با اجام حريكت هاي به قرار كن
اما به تدريج اندازه و تعداد حركات بد ( به سمت يايين) را كم كن *
function SiMULATED-ANNHALING( problem, schedule) reburns a solution state
inputs: problem a problem
schedule, a mapping from time to “temperature”
local variables: current, anode
next, anode
7 a “temperature” controling prob. of downward steps
current Maxe-Nonn(|vrrtat-Starefprobierd)
for t+ 1 t0 00 do
Te schedule
if P= 0 then return current
neat a randomly selected successor of current
Abe Vaturfneat] ~ VaLunfeurent]
if AF > O thon current nezt
else current « nezt only with probability كك 7
60 داشگاه تمتي اسان دا
صفحه 60:
سردسازي شبیه سازي شده
وی مانند تپه نوردی می باشد اما در هر مرحله حالت
بعدي به طور تصادفی انتخاب مي شود.
اگر حالت بعدي انتخاب شده بهتر باشد. همواره به آن حالت
بعدي خواهیم رفت.
* در غیر این صورت. تنها با يك احتمال به آن حالت خواهيم رفت
و این انختمال به ضورت تمايي کاهش مي یابد:
val * احشاز م
e AE/T Tatas”
* میزان کاهش در هر مرحله :۸۴
61
دانشگاه صنعتي |
صفحه 61:
خواص جستجوي SA
* در مقادیر بالاتر] احتمال انجام حرکات بد (رفتن به سمت
پایین) بیشتر است (مانند جستجوي تصادفي رفتار مي کند).
* با کاهش ۲ این احتمال کاهش يافته و در 10 این احتمال به
صفر مي رسد. ( مانند تبه نوردي رفتار مي كند)
* هی توانن تابن کرد که آگو ۲ بهءافناژه کاقی آرام کاجشی یابتبا
احتمال نزدیک به یک 5 یک پاسخ بهینه را خواهد یافت.
62
صفحه 62:
جستجوی پر توی Local Beam Search (leo
* شروع با ا حالت که به طور تصادفی ایجاد شده اند.
* در هر تکرار, تمام فرزندان براي هر حالت تولید مي شوند.
اگر يكي از آنها حالت هدف بود جستجو متوقف مي شود و در
غیر این صورت از میان لیست کامل فرزندان > تا از بهترین ها انتخاب مي
شوند و مرحله بالا تکرار مي شود.
تفاوت با جستجوي با شروع مجدد تصادفي
* در يك جستجوي با شروع مجدد تصادفي, هر فرآیند جستجو به طورمستقل از
بقیه اجرا مي شود.
* در يك جستجوي پرتوي محلي, اطلاعات سودمند در بین 1 جستجوي موازي رد و
بدل مي گردد.
63
صفحه 63:
جستجوي پر توي اتفاقي Stochastic beam
searc rch.
* مشکل جستجوي پرتوي محلي
* این روش ممکن است از نبود تنوع بین ۷ حالت رنج ببرد. به سرعت تمامي آنها
در محدوده كوچكي از فضاي حالت جمع شوند.
* جستجوي پرتوي اتفاقي
* به جاي انتخاب > بهترین از مجموعه پسينهاي منتخب 6 پسین را به صورت
تصادفی انتخاب کند.
* احتمال انتخاب هر پسین خاص تابعي از بازندگي آن
* الگوریتم ژنتیک
* نمونه اي از جستجوي پرتوي اتفافي که تولید حالتهاي پسین علاوه بر تغییر يك
حالت. از ترکیب دو حالت والد نیز (ترکیب جنسي) انجام مي شود.
64
صفحه 64:
function GENETIC-ALGORITHM( populztion. FITNESS-FN) returns an individual
Input: population, a set of individuals
FITNESS-FN. a function that measures the fitness of an individual
repeat
new_population <— empty set
loop for {from 1 to SIZE(populatiou) do
x RANDOM SELECTION(populetion, FITNESS FN)
¥y —RANDOM_ SELECTION (population. FITNESS FN)
child REPRODUCE(s,)
if (small random probability) then cfd —MUTATE( child)
add chifd'to new population
population <— new population
until some individual is fit enough or enough time has elapsed
return the best individual in population, according to FITNESS-FN
65 تعود دي تمتوان وار
صفحه 65:
مثال الگوربتم ژنتیک: 10 7 وزیر
]32742 [-| 32748552 / وت | 24748552
La 247148552 24752413 |—+| 24752411 32752411
32124 |+— | 32752124 | 327523111 2% 20 | 24415124
244151011310 | “24415124 14% 11 | 32543213
fay oe) 8 ۵ 0
Initial Population Fitness Function Selection Cioss-Over ‘Mutation
* تابع برازندگي : تعداد جفت وزیر هايي که یکدیگر را تهدید
نمي کنند. (مینیمم: صفره ماکزیمم: 28-7/2*8)
۴ 24+23+20+11)124( = 31%
24+23+20+11)/23( = 29%
Forel yp oS lye gate ts 66
صفحه 66:
مثال الگوریتم ژنتیک: 90 7 وزیر
67 داشگ صنمتي اسان دنه بق و Forel
صفحه 67:
جستجوی 0۳1۳6
* تا کنون تمام الگوریتم هاي مطرح شده 0۴۲11۲16 بودند.
al, Offline ° حلقبااز اجولیآنم عیراست
* 001106 محاسبه و عمل صويتيكدر ميان
* جستجوي 001106 براي محیط هاي پویا و نيمه پویا ضروري
مي باشد
* در نظر گرفتن تمامي امکان هاي مختلف غير ممکن است
اننتفادهنشدهدر مسائل اکتشافی
* حالت ها و اعمال ناشناخته 7
* مثال: يك روبات در يك محیط جدید. يك نوزاد و ..
68
نشگاه صتعتي اصفهان دانشکد
صفحه 68:
مسائل جستجوی 0۳۱116
a دانش عامل:
* عمل (ها): لیست اعمال مجاز در حالت 5
* تابع هزینه گام « پس از تعیین 5) (5 ,2 ,05
GOAL-TEST(s) *
* فرضیات
۶ عامل مي تواند حالت قبلي را تش تشخیص دهد
* اعمال قطعي هست:
* دستيابي به هيوربستيك قابل قبول (9)5
69
صفحه 69:
مسائل جستجوي 0۳1106
* هدف: رسیدن به حالت هدف با حداقل هزینه
* هزینه - کل هزینه مسیر پیموده شده
با هزینه مسیر راه حل در IE
که فضای جستجو شناخته شده باشد
5 نسبت رقابتي - مقایسه
* می تواند نا محدود باشد
* مثلا در مواردي که عامل به طور تصادفي به يك بن بست مي رسد
9 فضاي حالت قابل کاوش امن
* از هر حالت دست يافتني حداقل یک حالت هدف قابل دسترس باشد
* مثلا فضاهاي حالت با اقدامات قابل برگشت
25350005 70
صفحه 70:
مسائل جستجوي 0۳1106
Mal |S ی
i | ۹
۳ 5
* حالت ها ملاقات شده ۵ و 5 حالت بعدی؟
* در يكي از فضاهاي حالت شکست مي خورد
* هيج الگوريتمي نمي تواند از بن بست ها در تمامي فضاهاي حالت اجتناب کند
71
صفحه 71:
مسائل جستجوي 0۳1106
Y
sal
SA es
1 3 اي 5
9 ااا
1 |
هو ves
N\A
وس
يك محیط 2 بعدي را تصور کنید که حریف قادر است در حين کاوش
glad pole حالت را بسازد
* باعث مي شود یک کارگزار جستجوي برخط یک مسیر اجبارا ناکارامد
را به سمت هدف دنبال كند. 00
72 داشگ صنمتي اسان دنه بق و Forel
صفحه 72:
کارگزارهاي جستجوي 0۳116
۶ عامل يك نقشه از محيط نگهداري مي کند
7 نقشه بر اساس ورودي ادراكي بهنگام مي شود
- از این نقشه براي انتخاب عمل بعدي استفاده مي شود
* به تفاوت مثلا با ۸* دقت کنید ۱
* يك نسخه 001/06 تنها مي تواند گره اي را گسترش دهد که به طور
فيزيكي در آن قرار داشته باشد.
* براي اجتناب از جابجايي در عرض درخت بهتر است گره ها را به
ترتب معلي کستوش دهیم. مثلا جستجوي اول عمق. جستجوي
وه
73
صفحه 73:
کار گزارجستجوي 01016 با کاوش اول عمق
function ONLINE-DFS-AGENT(s) returns an action
input: 57 a percept identifying current state
static: resnfta table indexed by action and state, initially empty
tmexplored, a table that lists for each visited state, the action not yet tried
unbackiracked, « table 1
sa, the previous state and action, initially null
I lists for each visited state, the backtrack not yet tried
if GOAL-TEST(s) then return stop
]۱ state then unexplored's |< ACTIONS(s)
if sis not null then do
resulf.as] — 8°
add sto the front of nnhackedtracked 5]
if uueaplored.s is empty then
if unbackirackedd sis empty then return stop
else a an action bsuch that resid, s]-POP(unbackrracked s])
else a POP(uexplored’s 1)
ses
ose معي 4
صفحه 74:
جستجوي محلي online
* جستجوي تپه نوردي 01۱11116 مي باشدا!
* يك حالت ذخیره شده است
۶ عملکرد بد به دلیل وجود ماکزیمم های محلی
* شروع مجدد تصادفی غیر ممکن است
* راهکار 1: گام برداشتن تصادفی random walk
* یکی از اقدامات موجود حالت فعلی را به صورت تصادفی تولید
* مي توان به اقداماتي که تا کنون امتحان نشده اند احتمال بالاتري
داد.
75
صفحه 75:
جستجوی محلی online
* گام برداشتن تصادفي !۷۷۵ ۲3000
* اگر فضا متناهي باشد گام برداشتن تصادفي در نهایت یک هدف را
يبدا مي كند يأ کاوشهایش را کامل مي کند.
* این فرایند ممکن است خيلي کند باشد ( مي تواند حالات بسياري
را به صورت نمايي تولید کند)
76
صفحه 76:
جستجوی محلی online
راهکار 2: اضافه نمودن حافظه به تپه نورد
* ذخیره بهترین تخمین فعلي ( 5 از هزینه رسیدن به هدف
۴ (۲۱65 در لبتتا تخمينهيوريستيك (5) ميباشد.
* يس از آن بر اساس تجربه بهنگام مي شود.
* هزینه تخميني رسیدن به هدف از طریق همسایه اي مانند 5"
هزینه رسیدن به 5 " به علاوه ي هزینه ي تخميني رسیدن به هدف
از انجاست يعني ('11)5+ ('5,83,5)©
77
صفحه 77:
*Learning real-time A
apf BY 1 PNA a <P
8 هل( aoe
تس بل 2( 2 رفيا
fe Nok ما = 1
=> 8 9۱ دص( )3( ‘ale
oot (3) 0 ۲ بت
= حر 2 PN og fT
pare پم L(A) jae تم و )سلم( و /جله
Nef es ee ee ی
ont 9 و نا as 3) Dome
0
78
1
(a)
(b)
©
@
صفحه 78:
*Learning real-time A
function LRTA*-COST (s, 4 $77) return on cost estanate
if 5°15 undefined the return ii)
else return o(s 2, 5)+ Als]
function LRTA*-AGENT (s} return an action
Input: 5” a pescept identifying eusent stare
Static: zesul, table mdexed by action and state, mally empty
H,atable of cost estimates indexad by state, initially empty
sa the provious state and action, اه اور
ifGOAL. TEST (5) then return siop
ifs 15 anew state (uot m A) then As] Ls)
unless sis null
resus] 5
Hfs] © MIN LRTA'-COST (6, ]ملعم بن 3, 10
be ACTIONS (9)
2am action bin ACTIONS (s)) that minimizes LRTA* COST (7 6 resuit[6. 51. 2
79
صفحه 79:
يادگيري در جستجوي 0۳1186
* نتیجه هر اقدام در هر حالت
* در محيطهاي معین تنها یک تجربه براي هر اقدام كافي است
* براوردهاي دقیق تر از ارزش هر حالت
* با استفاده از قوانین به روزاوري محلي مشابه 81 1*
* به مجرد تعیین دقي
* يادگيري مفهوم اعمال
* اقدام ملا مختصات ۲ را افزايش مي دهد مگر اينکه ديواري بر سر
راه قرار داشته باشد.
مقادیر تپه نوردي محض راهبرد بهینه است.
55 80