1
هوش مصنوعی
فصل چهارم
جست و جوی آگاهانه و اکتشاف
2
هوش مصنوعی Artificial Intelligence
فهرست
متدهای جست و جوی آگاهانه
یادگیری برای جست و جوی بهتر
جست و جوی محلی و بهینه سازی
جست و جوی محلی در فضاهای پیوسته
عاملهای جست و جوی Online
3
جست و جوی آگاهانه و اکتشاف
متدهای جستجوی آگاهانه
بهترین جستجو
حریصانه
A*
IDA*
RBFS
MA* و SMA*
جستجوی محلی و بهینه سازی
تپه نوردی
شبیه سازی حرارت
پرتو محلی
الگوریتمهای ژنتیک
4
جست و جوی آگاهانه و اکتشاف
تعاریف
تابع هزینه مسیر، g(n) : هزینه مسیر از گره اولیه تا گره n
تابع اکتشافی، h(n) : هزینه تخمینی ارزان ترین مسیر از گره n به گره هدف
تابع بهترین مسیر، h*(n) : ارزان ترین مسیر از گره n تا گره هدف
تابع ارزیابی، f(n) : هزینه تخمینی ارزان ترین مسیر از طریق n
f(n): g(n) + h(n)
f*(n) : هزینه ارزان ترین مسیر از طریقn f*(n): g(n) + h*(n)
5
جست و جوی آگاهانه و اکتشاف
A
B
C
D
E
F
G
H
I
K
M
L
N
O
3
P
Q
J
W
V
X
Y
Z
R
S
T
U
1
1
2
1
3
3
2
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
1
2
5
3
0
1
3
2
3
1
2
2
1
1
2
1
0
2
1
3
1
2
3
3
2
جستجوی حریصانه
6
جست و جوی آگاهانه و اکتشاف
A
B
C
D
E
F
G
N
O
3
X
1
1
2
1
1
1
1
3
1
2
5
3
0
3
1
3
2
جستجوی حریصانه
7
جست و جوی آگاهانه و اکتشاف
جستجوی حریصانه
A
F
G
H
I
M
L
N
O
P
Q
W
V
X
Y
Z
R
S
T
U
1
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
3
2
3
1
2
2
1
1
2
1
0
2
1
3
1
2
3
3
3
8
جست و جوی آگاهانه و اکتشاف
جستجوی حریصانه
A
9
جست و جوی آگاهانه و اکتشاف
جستجوی حریصانه
کامل بودن: خیر
اما اگر h = h* آنگاه جستجو کامل میشود
بهینگی: خیر
اما اگر h = h* آنگاه جستجو کامل میشود
پیچیدگی زمانی:
اما اگر h = h* آنگاه
پیچیدگی فضا:
اما اگر h = h* آنگاه
کامل بودن:
بهینگی:
10
جست و جوی آگاهانه و اکتشاف
جستجوی A*
A/5
B/4
C/4
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
2
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
1
1
1
1
3
3
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
11
جست و جوی آگاهانه و اکتشاف
جستجوی A*
A/5
12
جست و جوی آگاهانه و اکتشاف
جستجوی A*
A/5
B/1
C/4
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
2
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
1
1
1
1
3
3
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
13
جستجوی A*
جست و جوی آگاهانه و اکتشاف
A/5
14
جستجوی A*
جست و جوی آگاهانه و اکتشاف
A/5
B/1
C/9
D/5
E/1
F/3
G/2
H/2
I/3
K/0
M/2
L/3
N/1
O/3
2
P/3
Q/1
J/1
W/1
V/2
X/0
Y/2
Z/1
R/2
S/2
T/1
U/1
1
1
1
1
3
3
3
3
2
3
2
3
1
1
1
2
3
2
1
1
1
3
2
3
15
جستجوی A*
جست و جوی آگاهانه و اکتشاف
A/5
16
جستجوی A*
جست و جوی آگاهانه و اکتشاف
کامل بودن: بله
بهینگی: بله
پیچیدگی زمانی:
اما اگر h = h* آنگاه
پیچیدگی فضا:
اما اگر h = h* آنگاه
17
جست و جوی آگاهانه و اکتشاف
h ≤ h*
h ≤ h*
/
جستجوی A*
18
جست و جوی آگاهانه و اکتشاف
جستجوی A*
h ≤ h*
h ≤ h*
/
19
جست و جوی آگاهانه و اکتشاف
A/100
B/80
C/95
E/86
F/78
G/90
T/60
H/80
J/82
N/72
L/80
K/85
W/52
X/58
M/75
Y/47
Z/50
O/78
P/79
D/90
M/75
I/87
P/79
O/78
U/81
V/83
T/60
R/20
W/52
X/58
Y/47
Z/50
S/70
10
جستجوی A* و اجتناب از گره های تکراری
هزینه هر مرحله 10 میباشد
20
جست و جوی آگاهانه و اکتشاف
جستجوی A* و اجتناب از گره های تکراری
A/100
21
جست و جوی آگاهانه و اکتشاف
مثال دیگر از جستجوی A*
f(n)=g(n) + h(n)
22
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
جستجوی Bucharest با شروع از Arad
f(Arad) = g(Arad)+h(Arad)=0+366=366
23
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََArad را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393
f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447
f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449
بهترین انتخاب شهر Sibiu است
24
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََSibiu را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646
f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415
f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671
f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+ h(Rimnicu Vilcea)=220+192=413
بهترین انتخاب شهر Rimnicu Vilcea است
25
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََRimnicu Vilcea را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
f(Craiova)=c(Rimnicu Vilcea, Craiova)+h(Craiova)=360+160=526
f(Pitesti)=c(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417
f(Sibiu)=c(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553
بهترین انتخاب شهر Fagaras است
26
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََ Fagaras را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591
f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450
بهترین انتخاب شهر Pitesti !!! است
27
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
ََ Pitesti را باز کرده و f(n) را برای هر یک از زیربرگها محاسبه میکنیم:
f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418
بهترین انتخاب شهر Bucharest !!! است
28
جست و جوی آگاهانه و اکتشاف
جستجوی A* در نقشه رومانی
29
جست و جوی آگاهانه و اکتشاف
جستجوی اکتشافی با حافظه محدود IDA*
ساده ترین راه برای کاهش حافظه مورد نیاز A* استفاده از عمیق کننده تکرار در زمینه جست و جوی اکتشافی است.
الگوریتم عمیق کننده تکرار A* IDA*
در جستجوی IDA* مقدار برش مورد استفاده، عمق نیست بلکه هزینه f(g+h) است.
IDA* برای اغلب مسئله های با هزینه های مرحله ای، مناسب است و از سربار ناشی از نگهداری صف مرتبی از گره ها اجتناب میکند
30
بهترین جستجوی بازگشتی RBFS
جست و جوی آگاهانه و اکتشاف
ساختار آن شبیه جست و جوی عمقی بازگشتی است، اما به جای اینکه دائما به طرف پایین مسیر حرکت کند، مقدار f مربوط به بهترین مسیر از هر جد گره فعلی را نگهداری میکند، اگر گره فعلی از این حد تجاوز کند، بازگشتی به عقب برمیگردد تا مسیر دیگری را انتخاب کند.
این جستجو اگر تابع اکتشافی قابل قبولی داشته باشد، بهینه است.
پیچیدگی فضایی آن O(bd) است
تعیین پیچیدگی زمانی آن به دقت تابع اکتشافی و میزان تغییر بهترین مسیر در اثر بسط گره ها بستگی دارد.
31
جست و جوی آگاهانه و اکتشاف
بهترین جستجوی بازگشتی RBFS
RBFS تا حدی از IDA* کارآمدتر است، اما گره های زیادی تولید میکند.
IDA* و RBFS در معرض افزایش توانی پیچیدگی قرار دارند که در جست و جوی گرافها مرسوم است، زیرا نمیتوانند حالتهای تکراری را در غیر از مسیر فعلی بررسی کنند. لذا، ممکن است یک حالت را چندین بار بررسی کنند.
IDA* و RBFS از فضای اندکی استفاده میکنند که به آنها آسیب میرساند. IDA* بین هر تکرار فقط یک عدد را نگهداری میکند که فعلی هزینه f است. RBFS اطلاعات بیشتری در حافظه نگهداری میکند
32
جست و جوی آگاهانه و اکتشاف
بهترین جستجوی بازگشتی در نقشه رومانی
33
جست و جوی آگاهانه و اکتشاف
بهترین جستجوی بازگشتی در نقشه رومانی
34
بهترین جستجوی بازگشتی در نقشه رومانی
جست و جوی آگاهانه و اکتشاف
35
جست و جوی آگاهانه و اکتشاف
جستجوی حافظه محدود ساده SMA*
SMA* بهترین برگ را بسط میدهد تا حافظه پر شود. در این نقطه بدون از بین بردن گره های قبلی نمیتواند گره جدیدی اضافه کند
SMA* همیشه بدترین گره برگ را حذف میکند و سپس از طریق گره فراموش شده به والد آن بر میگردد. پس جد زیر درخت فراموش شده، کیفیت بهترین مسیر را در آن زیر درخت میداند
اگر عمق سطحی ترین گره هدف کمتر از حافظه باشد, کامل است.
SMA* بهترین الگوریتم همه منظوره برای یافتن حلهای بهینه میباشد
36
جست و جوی آگاهانه و اکتشاف
جستجوی حافظه محدود ساده SMA*
اگر مقدار f تمام برگها یکسان باشد و الگوریتم یک گره را هم برای بسط و هم برای حذف انتخاب کند، SMA* این مسئله را با بسط بهترین برگ جدید و حذف بهترین برگ قدیمی حل میکند
ممکن است SMA* مجبور شود دائما بین مجموعه ای از مسیرهای حل کاندید تغییر موضع دهد، در حالی که بخش کوچکی از هر کدام در حافظه جا شود
محدودیتهای حافظه ممکن است مسئله ها را از نظر زمان محاسباتی، غیر قابل حل کند.
37
جستجوی گراف با A*
جست و جوی آگاهانه و اکتشاف
2
1
4
1
1
1
1
2
4
3
1
H/0
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
1
38
جست و جوی آگاهانه و اکتشاف
A/6
B/5
C/1
6
5
جستجوی گراف با A*
39
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
G/1
6
5
6
7
40
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
G/1
J/1
6
5
6
7
7
41
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
5
4
4
6
5
6
7
5
7
42
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
5
4
4
6
5
6
7
6
5
7
43
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
4
4
5
6
7
6
5
44
جست و جوی آگاهانه و اکتشاف
جستجوی گراف با A*
H/0
A/6
B/5
C/1
D/1
E/2
F/2
G/1
J/1
6
5
4
4
6
5
6
7
6
5
6
7
45
جست و جوی آگاهانه و اکتشاف
یادگیری برای جست و جوی بهتر
روشهای جست و جوی قبلی، از روشهای ثابت استفاده میکردند.
عامل با استفاده از فضای حالت فراسطحی میتواند یاد بگیرد که بهتر جست و جو کند
هر حالت در فضای حالت فرا سطحی، حالت(محاسباتی) داخلیِ برنامه ای را تسخیر میکند که فضای حالت سطح شیء، مثل رومانی را جست و جو میکند
الگوریتم یادگیری فراسطحی میتواند چیزهایی را از تجربیات بیاموزد تا زیردرختهای غیر قابل قبول را کاوش نکند.
هدف یادگیری، کمینه کردن کل هزینه، حل مسئله است
46
جست و جوی آگاهانه و اکتشاف
توابع اکتشافی
مثال برای معمای8
میانگِین هزینه حل تقریبا 22 مرحله و فاکتور انشعاب در حدود 3 است.
جست و جوی جامع تا عمق 22 :
با انتخاب یک تابع اکتشافی مناسب میتوان مراحل جستجو را کاهش داد
47
جست و جوی آگاهانه و اکتشاف
دو روش اکتشافی متداول برای معمای8
تعداد کاشیها در مکانهای نادرست
در حالت شروع
اکتشاف قابل قبولی است، زیرا هر کاشی که در جای نامناسبی قرار دارد، حداقل یکبار باید جابجا شود
48
جست و جوی آگاهانه و اکتشاف
دو روش اکتشافی متداول برای معمای8
مجموعه فواصل کاشیها از موقعیتهای هدف آنها
در حالت شروع
چون کاشیها نمیتوانند در امتداد قطر جا به جا شوند, فاصله ای که محاسبه میکنیم مجموع فواصل افقی و عمودی است. این فاصله را فاصله بلوک شهر یا فاصله مانهاتان مینامند.
49
جست و جوی آگاهانه و اکتشاف
دو روش اکتشافی متداول برای معمای8
مجموعه فواصل کاشیها از موقعیتهای هدف آنها
قابل قبول است، زیرا هر جابجایی که میتواند انجام گیرد، به اندازه یک مرحله به هدف نزدیک میشود.
هیچ کدام از این برآوردها، هزینه واقعی راه حل نیست
هزینه واقعی 36 است
50
جست و جوی آگاهانه و اکتشاف
اثر دقت اکتشاف بر کارایی
فاکتور انشعاب موثر b*
اگر تعداد گره هایی که برای یک مسئله خاص توسط A* تولید میشود برابر با N و عمق راه حل برابر با d باشد، آن گاه b* فاکتور انشعابی است که درخت یکنواختی به عمق d باید داشته باشد تا حاوی N+1 گره باشد
فاکتور انشعاب موثر معمولاً برای مسئله های سخت ثابت است
اندازه گیریهای تجربی b* بر روی مجموعه کوچکی از مسئله ها میتواند راهنمای خوبی برای مفید بودن اکتشاف باشد
مقدار b* در اکتشافی با طراحی خوب، نزدیک 1 است
51
جست و جوی آگاهانه و اکتشاف
اثر دقت اکتشاف بر کارایی
هزینه جست و جو
فاکتور انشعاب موثر
میانگین گره های بسط یافته در جستجویIDS و A* و فاکتور انشعاب موثر با استفاده ازh1 و h2
52
جست و جوی آگاهانه و اکتشاف
اثر دقت اکتشاف بر کارایی
اگر برای هر گره n داشته باشیم: h2(n) >= h1(n)
h2 بر h1غالب است
غالب بودن مستقیما به کارایی ترجمه میشود
تعداد گره هایی که با بکارگیری h2 بسط داده میشود، هرگز بیش از بکارگیری h1 نیست
همیشه بهتر است از تابع اکتشافی با مقادیر بزرگ استفاده کرد، به شرطی که زمان محاسبه اکتشاف، خیلی بزرگ نباشد
53
جست و جوی آگاهانه و اکتشاف
الگوریتم های جست و جوی محلی و بهینه سازی
الگوریتم های قبلی، فضای جست و جو را به طور سیستماتیک بررسی میکنند
تا رسیدن به هدف یک یا چند مسیر نگهداری میشوند
مسیر رسیدن به هدف، راه حل مسئله را تشکیل میدهد
در الگوریتم های محلی مسیر رسیدن به هدف مهم نیست
مثال: مسئله 8 وزیر
دو امتیاز عمده جست و جوهای محلی
استفاده از حافظه کمکی
ارائه راه حلهای منطقی در فضاهای بزرگ و نامتناهی
این الگوریتمها برای حل مسائل بهینه سازی نیز مفیدند
یافتن بهترین حالت بر اساس تابع هدف
54
جست و جوی آگاهانه و اکتشاف
الگوریتم های جست و جوی محلی و بهینه سازی
55
جست و جوی تپه نوردی
جست و جوی آگاهانه و اکتشاف
حلقه ای که در جهت افزایش مقدار حرکت میکند(بطرف بالای تپه)
رسیدن به بلندترین قله در همسایگی حالت فعلی، شرط خاتمه است.
ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه میدارد
جست و جوی محلی حریصانه نیز نام دارد
بدون فکر قبلی حالت همسایه خوبی را انتخاب میکند
تپه نوردی به دلایل زیر میتواند متوقف شود:
بیشینه محلی
برآمدگی ها
فلات
56
جست و جوی آگاهانه و اکتشاف
انواع تپه نوردی:
تپه نوردی غیرقطعی، تپه نوردی اولین انتخاب، تپه نوردی شروع مجدد تصادفی
مثال: مسئله 8 وزیر
مسئله 8 وزیر با استفاده از فرمولبندی حالت کامل
در هر حالت 8 وزیر در صفحه قرار دارند
تابع جانشین: انتقال یک وزیر به مربع دیگر در همان ستون
تابع اکتشاف: جفت وزیرهایی که نسبت به هم گارد دارند
مستقیم یا غیر مستقیم
جست و جوی تپه نوردی
57
جست و جوی آگاهانه و اکتشاف
مثال جست و جوی تپه نوردی
الف- حالت با هزینه h=17 که مقدار h را برای هر جانشین نشان میدهد
ب- کمینه محلی در فضای حالت 8 وزیر؛ h=1
الف
ب
58
جست و جوی آگاهانه و اکتشاف
جست و جوی شبیه سازی حرارت
تپه نوردی مرکب با حرکت تصادفی
شبیه سازی حرارت: حرارت با درجه بالا و به تدریج سرد کردن
مقایسه با حرکت توپ
توپ در فرود از تپه به عمیق ترین شکاف میرود
با تکان دادن سطح توپ از بیشینه محلی خارج میشود
با تکان شدید شروع(دمای زیاد)
بتدریج تکان کاهش(به دمای پایین تر)
با کاهش زمانبندی دما به تدریج، الگوریتم یک بهینه عمومی را می یابد
59
جست و جوی آگاهانه و اکتشاف
جست و جوی پرتو محلی
به جای یک حالت، k حالت را نگهداری میکند
حالت اولیه: k حالت تصادفی
گام بعد: جانشین همه k حالت تولید میشود
اگر یکی از جانشین ها هدف بود، تمام میشود
وگر نه بهترین جانشین را انتخاب کرده، تکرار میکند
تفاوت عمده با جستجوی شروع مجدد تصادفی
در جست و جوی شروع مجدد تصادفی، هر فرایند مستقل از بقیه اجرا میشود
در جست و جوی پرتو محلی، اطلاعات مفیدی بین k فرایند موازی مبادله میشود
جست و جوی پرتو غیرقطعی
به جای انتخاب بهترین k از جانشینها، k جانشین تصادفی را بطوریکه احتمال انتخاب یکی تابعی صعودی از مقدارش باشد، انتخاب میکند
60
جست و جوی آگاهانه و اکتشاف
الگوریتم های ژنتیک
شکلی از جست و جوی پرتو غیر قطعی که حالتهای جانشین از طریق ترکیب دو حالت والد تولید میشود
61
الگوریتم های ژنتیک
جست و جوی آگاهانه و اکتشاف
جهت اولیه
تابع برازش
انتخاب
تقاطع
جهش
62
جست و جوی آگاهانه و اکتشاف
جست و جوی محلی در فضاهای پیوسته
گسسته در مقابل محیط های پیوسته
در فضاهای پیوسته، تابع جانشین در اغلب موارد، حالتهای نامتناهی را بر میگرداند
حل مسئله:
گسسته کردن همسایه هر حالت
استفاده از شیب منظره
روش نیوتن رافسون
63
جست و جوی آگاهانه و اکتشاف
عاملهای جست و جوی Online و محیطهای ناشناخته
تا به حال همه الگوریتمها برون خطی بودند
برون خطی(Offline):راه حل قبل از اجرا مشخص است
درون خطی(Online):با یک در میان کردن محاسبات و فعالیت عمل میکند
جستجوی درون خطی در محیطهای پویا و نیمه پویا مفید است
آنچه را که باید واقعا اتفاق بیفتد، در نظر گرفته نمیشود
جست و جوی درون خطی ایده ضروری برای مسئله اکتشاف است
فعالیتها و حالتها برای عامل مشخص نیستند
مثال:قرار گرفتن روبات در محیطی جدید, نوزاد تازه بدنیا آمده
64
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
اطلاعات عامل
Actions(s): لیستی از فعالیتهای مجاز در حالت s
تابع هزینه مرحله ای c(s,a,s’): استفاده وقتی که بداند s’ نتیجه است
Goal-Test(s): آزمون هدف
عامل حالت ملاقات شده قبلی را تشخیص میدهد
فعالیتها قطعی اند
دسترسی به تابع اکتشافی قابل قبول h(s)
65
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
هدف: رسیدن به G با کمترین هزینه
هزینه: مجموع هزینه های مراحل مسیری است که عامل طی میکند
نسبت رقابتی: مقایسه هزینه با هزینه مسیری که اگر عامل فضای حالت را از قبل میشناخت، طی میکرد
در بعض موارد، بهترین نسبت رقابتی
نامتناهی است
ممکن است جستجو به یک حالت
بن بست برسد که نتوان از طریق آن به هدف رسید
66
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
دو فضای حالت که عامل جست و جوی Online را به بن بست میرسانند. هر عاملی حداقل در یکی از این دو فضا شکست می خورد
67
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
یک محیط دو بعدی که موجب میشود عامل جست و جویOnline مسیر دلخواه ناکارآمدی را برای رسیدن به هدف حل کند