Научен опит от миночистач
Принадлежи към раздела „Наука“
Два начина за прилагане на схемата MGA за решаване на проблема с отварянето на поле в сапьор
(игра в комплект с повечето операционни системи)
Задачата за отваряне на поле в сапьор е доста тривиална и има много специфично отдавна известно решение. Но смисълът на използването на подхода MGA не е да се реши проблем, който преди не е имал решение. Предвижда се да се демонстрира ефективността на подхода MGA за решаване на проблема при липса на първоначални данни за него и дори без да се знаят условията на проблема.
И така, какво се дава, ако нищо не се знае?
Има сензорна картина, тоест стандарт, например пиксел, изображение на полето на сапьора. В най-общия случай е възможно да се извършват различни действия във връзка с наличието на сетивна картина. Известна е и крайната цел - да се отвори цялото поле. Важно е да има различни начини за първоначално формулиране на тази цел.
В началния етап на търсенето на решение се планира да се определи какви действия водят до промяна в сензорната картина. Напълно възможно е да използвате GA за това. Да приемем, че този етап е преминал и е установено, че над клетките могат да бъдат извършени 3 действия: отворете, поставете мина, щракнете двукратно (отворете съседни клетки, ако наоколо има достатъчно мини). Не е толкова лесно да се открие последното действие (намерих го след половин година), но проблемът може да бъде решен и без него. В допълнение към търсенето на действия, които водят до промяна на екрана, можете също да изберете минималната променлива област на сензорната картина (клетка) и да определите всички състояния, присъщи на тази област. Нека ви напомня, че сапьорът има доста ограничен брой от тези състояния, 11 броя: 9 цифри, затворено поле, мина. Отбелязвам, че този етап дори не изисква разбиране на това, което е изобразено в мината или номера (и ако броят, кой).
Така че всички необходими компоненти за стартиране на GA, насочени директно към намиране на решение, са налице. Съвсем логично е, тъй като моделираме работата на централната нервна система, да търсим решение под формата на стимул - реакция. В този случай стимул е промяна в сензорната картина или състоянието на една или определен брой клетки. Реакцията може да се счита за едно от трите посочени по-рано действия. По-точно, действието, което трябва да се извърши върху клетката, зависи от текущото състояние на клетките в полето, или по-точно, клетките около него, но това обстоятелство може да бъде открито още по време на работата на GA. Задачата може да бъде разделена на две части: търсене на шаблони, тоест съвкупността от клетки в полето, от които зависи текущото състояние на клетката. Търсете стойностите на клетките на шаблона, при които може да се извърши действие върху тази клетка, без страх от прекратяване на играта. Опростен неврон може да се използва за извършване на действие, когато желаният модел се появи в сензорната картина. Неговите входни сигнали ще бъдат състоянието на клетките на шаблона, а изходният сигнал ще бъде действие, насочено към промяна на състоянието на съответната клетка. Ако се появи съответен сигнал, невронът ще се възбуди и ще изпрати сигнал по у аксона, в резултат на което действието ще се извърши автоматично. Сред популациите от този вид неврони ще бъде избран GA. Крайните резултати от този подбор могат да бъдат предсказани въз основа на познанията за евристичното решение. Например:
По-общо:
Където * не е отворено поле.
Показани са шаблони за засаждане на мина в долния ляв неотворен ъгъл.
можете безопасно да отворите всички неотворени полета.
Всеки може сам да изведе други типове шаблони. Просто трябва да вземете предвид, че освен показаните шаблони с девет точки, има опции за шаблони, които съдържат повече полета.
Какви са характеристиките на този подход за намиране на решения?
Първото нещо, което може да се отбележи, е, че дори за толкова проста задача като сапьор, решение се търси постепенно, тъй като се натрупват полезни шаблони.
Второ, резултатът от оптимизацията ще бъде невронна мрежа, която ще може да отвори почти мигновено всички полета, които не съдържат места с неясен избор.
Можете също така да опитате да изберете двуслойна невронна схема, където вторият слой ще реализира работата на GA за избор на полезни неврони от първо ниво, чийто принцип е описан по-рано. Не знам колко широко се използват невронни мрежи за решаване на такива формализирани проблеми, но решаването на такъв проблем от невронна мрежа при липса на първоначални идеи за това ще бъде важен прецедент за тяхното приложение. Важно е да се спомене следното свойство на вече отстранената грешка на невронната мрежа на първия невров слой. Броят на циклите на нейното действие, необходим за пълното отваряне на полето в сапьора, зависи логаритмично от броя на клетките на полето. За системи с линейна архитектура броят на тактовите цикли е от порядъка на квадрата на броя на клетките.