Что нового

Использование генетических алгоритмов в AutoIt

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Любопытства ради интересно узнать, кто-нибудь пробовал реализовать ГА в AutoIt?

Я столкнулся в самом начале с проблемой преобразования гена в набор команд, где в соответствии с геном и арностью необходимо составить дерево команд.

Вроде бы можно было бы сгенерировать выражение для Execute, но как быть с функциями синуса или условным оператором?
 

Medic84

Омега
Команда форума
Администратор
Сообщения
1 575
Репутация
335
Re: [Математика] Использование генетических алгоритмов в AutoIt

Если мне не отшибло память, то генетические расчеты как бы запрещены законом РФ :D
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Re: [Математика] Использование генетических алгоритмов в AutoIt

Medic84, вам лиж бы поприкалываться :shok:fftop: Лучше б подсказали чего умного :smile:
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Re: [Математика] Использование генетических алгоритмов в AutoIt

Теперь рождаются новые вопросы. С какой стати генетические расчеты запрещены? Какое отношение они имеют к генетическим алгоритмам?

То что вопрос не верно составил теперь понятно. Вот есть набор цифр-генов:
1025678. Которые обозначают:
0 - умножение двух операндов
1 - сложение двух операндов
2 - деление
5, 6, 7, 8 индексы некоторых констант.

Собственно из 1025678 нужно получить строку для вычисления, которая получается (5*6)+(7*8)

Вроде бы в ГА это зовется построением дерева
 

Suppir

Продвинутый
Сообщения
967
Репутация
62
Мне тоже интересны генетические алгоритмы. Кто-нибудь может показать простейшую программу на AutoIt, которая выполняет какое-нибудь полезное действие?
 

Kalisnik

Эволюция
Сообщения
295
Репутация
63
На счет законов РФ, к моему сожалению, я мало осведомлен. Но могу предположить, что закон обсуждаемый выше (если Medic84'у не изменяет память) касается лишь генома человека? А вот комарам, наверно, можно отомстить. :smile: Только лучше это делать не в AutoIt'е.
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Вообще сабж был только о том, что бы построить код на AutoIt из дерева терминалов и нетерминалов...
 

Kalisnik

Эволюция
Сообщения
295
Репутация
63
OffTopic:
Вообще ни чего не знал про существование таковых алгоритмов. Тема и ссылка выше весьма заинтересовала. Так что присоединяюсь к просьбам предоставить в этой теме простейший генетический алгоритм, пусть даже бесполезный - главное корректный! :blink:
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Сейчас напишу реализацию одного простого алгоритма, а завтра подумаю над тем, который хотел реализовать... Вот еще интересная ссылка http://habrahabr.ru/blogs/algorithm/111811/
 

Dark-Side

Знающий
Сообщения
72
Репутация
17
Только в понедельник читал про ГА на хабре и тоже хотел скинуть эту ссылку :smile:

Присоединяюсь, было бы интересно увидеть реализацию ГА на AutoIT с преподробнейшим описанием т.к. я слышу об этом ГА, пожалуй, во второй или третий раз.
На википедии (я точно не знаю - не проверял), должны быть примеры кода ГА на разных языках, надо будет как-нить глянуть.
 

Nik_rus

Python The Snake.
Сообщения
214
Репутация
62
На AutoIT ИМХО будет неприемлимо... Ну... медленно и не кросс-платформенно.
Реализовать ГА и нейросети для каптч у меня получилось только на Python.
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Всё возможно и уже работает, доделаю выложу :laugh:

Честно говоря оно не работает как надо, но уже надоело что-то делать, вечером продолжу, вероятно, а так можете посмотреть если интересно.

Код:
#include <Array.au3>
#include <GuiConstantsEx.au3>
#include <GDIPlus.au3>

Func StartView()
	Global $hGUI, $hGraphic

    ; Create GUI
    $hGUI = GUICreate("Обзор", 400, 300)
    GUISetState()
	_GDIPlus_Startup ()
    $hGraphic = _GDIPlus_GraphicsCreateFromHWND ($hGUI)
    $hPen = _GDIPlus_PenCreate()
EndFunc

Func DrawRect($aToDraws)
	_GDIPlus_GraphicsDrawLine($hGraphic, 0, 10, 410, 10)
	$hPen1 = _GDIPlus_PenCreate(0xFFFF0000)
	$hPen2 = _GDIPlus_PenCreate(0xFF000000)
	$hPen3 = _GDIPlus_PenCreate(0x7F000000)
	For $k=0 To UBound($aToDraws)-1
		If $k = 0 Then
			$x = 2
		Else
			$x = 400/UBound($aToDraws)*$k
		EndIf
		$iViewVar = $aToDraws[$k]
		$iText = -10
		
		If $iViewVar/10 > 295 Then
			$iViewVar = 2950
		ElseIf $iViewVar/10 < 0 Then
			$iText = 0
			$iViewVar = 0
		EndIf
		_GDIPlus_GraphicsFillRect($hGraphic, 0, 0, 400, 300, $hPen3)
		_GDIPlus_GraphicsDrawRect($hGraphic, $x-2, $iViewVar/10-2, 4, 4, $hPen1)
		_GDIPlus_GraphicsDrawRect($hGraphic, $x-1, $iViewVar/10-1, 2, 2, $hPen2)
		_GDIPlus_GraphicsDrawString($hGraphic, $aToDraws[$k], $x-2, $iViewVar/10+$iText, 'Arial', 7)
	Next
EndFunc

Func ThisLive(ByRef $aResultsCalc, ByRef $index)
	ConsoleWrite('Живет особь с результатом '&$aResultsCalc[$index]&@CRLF)
	
	$iViewVar = $aResultsCalc[$index]
	$iText = -10
	
	If $index = 0 Then
		$x = 2
	Else
		$x = 400/UBound($aResultsCalc)*$index
	EndIf
		
	If $iViewVar/10 > 295 Then
		$iViewVar = 2950
	ElseIf $iViewVar/10 < 0 Then
		$iText = 0
		$iViewVar = 0
	EndIf
	
	_GDIPlus_GraphicsDrawString($hGraphic, '.', $x-8, $iViewVar/10+$iText, 'Arial', 7)
EndFunc

Func EndView()
	Do
	Until GUIGetMsg() = $GUI_EVENT_CLOSE
	_GDIPlus_GraphicsDispose ($hGraphic)
	_GDIPlus_Shutdown ()
EndFunc

Func FirstGenerate(ByRef $iNumPerson, ByRef $iNumChrom, ByRef $iStartRnd, ByRef $iFinishRnd)
	Dim $aPerons[$iNumPerson][$iNumChrom]	;Задаем массив
	
	For $i=0 To $iNumPerson-1				;Выбираем особь
		For $j=0 To $iNumChrom-1			;И хромосому
			$aPerons[$i][$j] = Random($iStartRnd, $iFinishRnd, 1)	;Задаем случайное число
		Next
	Next
	
	Return $aPerons
EndFunc

Func CalcResult(ByRef $aChromes)
	Dim $sFunction		= '3*a+6*b-8*c+9*d'		;3*15+6*200-8*151+9*7=100
	Dim $aConstant[4]	= ['a', 'b', 'c', 'd']	;хотел создать Enum но не разобрался с ним
	
	$sFunctionWithChromes = $sFunction
	For $i=0 To UBound($aConstant)-1			;подставляем в функцию пришедшие значения
		$sFunctionWithChromes = StringReplace($sFunctionWithChromes, $aConstant[$i], $aChromes[$i])
	Next

	$iResult = Execute($sFunctionWithChromes)
	
	Return $iResult
EndFunc

Func Fintess(ByRef $aGenerate, ByRef $aResultsFintess, ByRef $iNeededResult)
	Dim $iNumResults = UBound($aResultsFintess)
	Dim $aFitness[$iNumResults][2]	;Приспособленность особи в процентах, первый эл. массива номер особи
	
	$iCostStep	= 100/(_ArrayMax($aResultsFintess) - $iNeededResult)	;Цена деления шкалы
	
	For $i=0 To $iNumResults-1		;Перебираем все реультаты
		$aFitness[$i][0] = $i		;Сохраняем номер особи в 0ом элементе
		$aFitness[$i][1] = Abs($aResultsFintess[$i])*$iCostStep	;Приспособленность особи в процентах
	Next
	
	Return $aFitness
EndFunc

StartView()

Global $iNeededResult = 100		;Необходимый результат функции
$iNumPersons	= 12			;Число особей
$iNumChromos	= 4				;Число хромосом у каждой особи
$aGenerate		= FirstGenerate($iNumPersons, $iNumChromos, 0, 300)	;Генерируем первое поколение

Do
	Dim $aResultsCalc[$iNumPersons]
	Dim $iFindResult = 0
	For $i=0 To $iNumPersons-1	;Определяем приспособленность данной особи
		Dim $aChromesPersNow[$iNumChromos]	;Массив хромосм данной особи
		
		For $j=0 To $iNumChromos-1			;Сохраняем массив хромосом данной особи
			$aChromesPersNow[$j] = $aGenerate[$i][$j]
		Next
		
		$aResultsCalc[$i] = CalcResult($aChromesPersNow)
	Next
	DrawRect($aResultsCalc)	;Посмотреть что получилось 
	
	$aFitness	= Fintess($aGenerate, $aResultsCalc, $iNeededResult)	;Вычислим приспособленность особи
	_ArraySort($aFitness, 0, 0, 0, 1)	;Сортируем массив по возрастанию, вверху самые приспособленные
	
	$iMiddlePersons = UBound($aFitness)
	ConsoleWrite('Скрестим лучших, первых '&$iMiddlePersons&@CRLF)
	For $i=0 To $iMiddlePersons/2-1	Step 2;Возьмем половину первых-лучших особей
		Dim $aChromesPersNow1[$iNumChromos]
		Dim $aChromesPersNow2[$iNumChromos]
		
		ThisLive($aResultsCalc, $aFitness[$i][0])
		ThisLive($aResultsCalc, $aFitness[$i+1][0])
		For $ip1 = 0 To $iNumChromos-1	;Сохраняем наборы хромосом скрещиваемых особей
			If Random(0, 100, 1) Then
				$iMutant = Random(0, 300, 1)
			EndIf
			
			$aGenerate[$iMiddlePersons/2+$i][$ip1]		= $aGenerate[$aFitness[$i+Random(0, 1, 1)][0]][$ip1]+$iMutant
			$aGenerate[$iMiddlePersons/2+$i+1][$ip1]	= $aGenerate[$aFitness[$i+Random(0, 1, 1)][0]][$ip1]+$iMutant
		Next
	Next
	
	Sleep(200)
Until $iFindResult = 1

EndView()
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
qsort [?]
Судя по результат работы программы ошибка в логике или с переменными что-то напутал. Но всё реально и это радует!
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Помогите! Не могу решить задачу по приспособленности. В общем есть шкала от
100_________________до_____3300 (например), а на ней есть некоторое число, скажем 620
100______620_______________3300 и надо как то в процентах вычислить на сколько оно близко к 100.
Где 100 соответствует 100%, 3300 - 0%, а 620 - кто его знает%.

Даже не знаю, как решить, пробовал разбить шкалу на проценты, то есть 3300-100=3200, 3200/100=32 получается, что каждое число в 32 соответствует 1%.
Тогда выходит, что:
Код:
(3300-100)/32 = 100%
(2650-100)/32 = 79,68%
(620-100)/32 = 16,25%
(300-100)/32 = 6,25%
(101-100)/32 = 0,03%
(Вот пока писал половина задачи решилась) А как инвертировать, что бы первый результат был 0% а последний близкий к 100%? Надо писать так 100-(3300-100)/32

Сорри, что нафлудил, но иначе задача не решалась. Видимо в этом и была проблема в предыдущей версии. Сейчас проверил - и правда неправильно решает :whistle:

P.S. Кто-то говорил о медлительности AutoIt. Для тестов пришлось усложнить уравение (3*a+6*b-8*c+9*d=100) так, как AutoIt методом случайного подбора подбирал решение в среднем за 0.0295 секунды. А уравнение вида:
10*a+150*b+13*c+6*d+31*e+15*f+30*g+68*h+11*i+12*j+15*k+18*l=41142 подбирает за 6.2156 секунды, есть на чем тестить =)

А вот GUI уже тормозит, с отображение результата тайминг вычисления массивов выглядит так:
0.036 - пришел массив
0.0683 - пришел массив
0.0998 - пришел массив
0.1324 - пришел массив
0.1646 - пришел массив


А так без GUI:
0.0064 - пришел массив
0.0127 - пришел массив
0.019 - пришел массив
0.0253 - пришел массив
0.0316 - пришел массив
 

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4 020
Репутация
622
qsort
в ГА начальное значение подбирается случайным образом
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
qsort, не))) не совсем случайный Random называется) По тестам то длинное уравнение рандом решает за такие промежутки времени, несколько тестов:
5.7535
15.1146
3.5063
10.7448
14.0875
0.1639
9.3635
6.5453
4.5095
38.9259

Но если посчитать число вариантов для решения метдом брутфорса получится столько комбинаций 300^12=531441000000000000000000000000, если решить, что решение может быть только одно (а это не так, как показывают тесты), то это как бы не очень быстрое дело ;)
Kaster, да, я пока селекцию не сделал, вот и решил протестировать сколько времени случайный подбор займет.
 

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4 020
Репутация
622
OffTopic:
qsort
я заметил что ты любишь дополнять свои посты даже если после него были другие, не говоря уже о вставке цитат из последующих постов. это не очень правильно.
 

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4 020
Репутация
622
qsort [?]
Свои посты я дополняю, но никак не редактирую
как раз обратное приветствуется. в любом случае, это был совет. если тебе хочется быть автором сообщений вне хронологической цепочки - твое право.

Mr. Anderson
переношу тему в раздел для общения, если ты не против
 
Автор
M

Mr. Anderson

Новичок
Сообщения
122
Репутация
4
Написал, опять в чем то ошибся :mad: работает не так, но уже интереснее :whistle:

Код:
#include <Array.au3>
#include <GuiConstantsEx.au3>
#include <GDIPlus.au3>

#region ПАРАМЕТРЫ
Global $iNumPopulation	= 20
Global $iGen			= 12
Global $iCalcSentence	= '10*a+150*b+13*c+6*d+31*e+15*f+30*g+68*h+11*i+12*j+15*k+18*l';'3*a+6*b-8*c+9*d'
Global $iNeededResult	= 41142
Global $iStartGen		= 0
Global $iEndGen			= 300
Global $view			= 1
#endregion

#region ФУНКЦИИ
Func StartView()
	Global $hGUI, $hGraphic

	$hGUI = GUICreate("Обзор", 800, 800)
    GUISetState()
	_GDIPlus_Startup()
    $hGraphic = _GDIPlus_GraphicsCreateFromHWND ($hGUI)
EndFunc

Func DrawResults(ByRef $aResults, ByRef $iNumPopulation, ByRef $iNeeded)
	_GDIPlus_GraphicsClear($hGraphic, 0xFFCCCCCC)
	;Вычисление цены пикселя
	$iDist	= Abs(_ArrayMax($aResults))-$iNeeded
	$iDownDist	= Abs(_ArrayMin($aResults))-$iNeeded
	If $iDist < $iDownDist Then $iDist = $iDownDist
	$iPixelSumm = 400/$iDist
	
	$iXStep		= 800/$iNumPopulation
	
	_GDIPlus_GraphicsDrawLine($hGraphic, 0, 400, 800, 400)
	$hPen1 = _GDIPlus_PenCreate(0xFF000000)
	$hPen2 = _GDIPlus_PenCreate(0xFFFF0000)
	
	For $p=0 To $iNumPopulation-1
		$iX = $iXStep*$p
		If $iX=0 Then 
			$iX = 2
		ElseIf $iX=800 Then
			$iX = 800-2
		EndIf
		
		$iY = ($aResults[$p]-$iNeeded)*$iPixelSumm+400
		If $iY > 795 Then
			$iY = 795
		ElseIf $iY < 5 Then
			$iY = 5
		EndIf
		
		_GDIPlus_GraphicsDrawRect($hGraphic, $iX-1, $iY-1, 3, 3, $hPen1)
		_GDIPlus_GraphicsDrawRect($hGraphic, $iX, $iY, 1, 1, $hPen2)
		_GDIPlus_GraphicsDrawString($hGraphic, $aResults[$p], $iX+2, $iY-5, 'Arial', 7)
	Next
EndFunc

Func EndView()
	Do
	Until GUIGetMsg() = $GUI_EVENT_CLOSE
	_GDIPlus_GraphicsDispose ($hGraphic)
	_GDIPlus_Shutdown ()
EndFunc

Func FirstGenerate(ByRef $iNumPopulation, ByRef $iGen, ByRef $iStartGen, ByRef $iEndGen, $iN = 1)
	Dim $aResult[$iNumPopulation][$iGen]
	
	For $i = 0 To $iNumPopulation-1
		For $j = 0 To $iGen-1
			$aResult[$i][$j] = Random($iStartGen, $iEndGen, $iN)
		Next
	Next
	
	Return $aResult
EndFunc

Func Fitness(ByRef $aPopulation, ByRef $iNumPopulation, ByRef $iGen, ByRef $iCalcSentence, ByRef $iNeededResult)
	Dim $aPercent[$iNumPopulation][2]	;Массив особь:приспособленность
	Dim $aResult[$iNumPopulation]		;Массив результатов
	Dim $aLetters[13] = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm']
	
	For $i = 0 To $iNumPopulation-1		;Берем первую особь
		$iStringCalc = $iCalcSentence	;Сохраняем выражение для вычисления в отдельную строку
		
		For $j = 0 To $iGen-1			;Берем первый ген и заменяем на него первую букву
			$iStringCalc = StringReplace($iStringCalc, $aLetters[$j], $aPopulation[$i][$j])
		Next
		
		$aResult[$i] = Execute($iStringCalc)	;Вычисляем результат выражения
		
		If $aResult[$i] = $iNeededResult Then	;Если это тот результат который нужен
			Return $i			;Сохраняем индекс особи
			ExitLoop			;Выходим из цикла, остальные особи уже не интересуют
		EndIf
	Next

	If $view Then DrawResults($aResult, $iNumPopulation, $iNeededResult)
	;Если всё же не было ни одого решения, вычислим приближенность особей к решению
	$iMax = _ArrayMax($aResult)
	$iMin = Abs(_ArrayMin($aResult))
	If $iMin > $iMax Then $iMax = $iMin
	
	$iDiv = ($iMax-$iNeededResult)/100
	For $i = 0 To $iNumPopulation-1
		$aPercent[$i][0] = $i
		$aPercent[$i][1] = 100-(Abs($aResult[$i]-$iNeededResult))/$iDiv
	Next
	
	Return $aPercent
EndFunc

Func Selection(ByRef $aSurvival, ByRef $aPopulation, ByRef $iNumPopulation, ByRef $iGen, ByRef $iEndGen)
	Dim $aCombineArray[$iNumPopulation][$iGen+1]
	;Соединяем массив в массив вида 
	For $i=0 To $iNumPopulation-1
		For $j=0 To $iGen
			If $j <> $iGen Then
				$aCombineArray[$i][$j] = $aPopulation[$i][$j]
			Else
				$aCombineArray[$i][$j] = $aSurvival[$i][1]
			EndIf
		Next
	Next
	
	;Удаляем слабых
	_ArraySort($aCombineArray, 1, 0, 0, $iGen)
	For $i = UBound($aCombineArray)/2 To UBound($aCombineArray)-1
		_ArrayDelete($aCombineArray, $i)
	Next
	
;~ 	ConsoleWrite(@TAB&'лучшая особь '&$aSurvival&'[')
;~ 	For $i=0 To $iGen-1
;~ 		ConsoleWrite($aCombineArray[0][$i]&'|')
;~ 	Next
;~ 	ConsoleWrite('] '&@CRLF)
	
	;Генерация новых особей
	Dim $aEnclave[4][$iGen]						;Временное хранилище
	Dim $aDiffGen[$iGen]						;Шаг отличия генома
	Dim $aNewGenerate[$iNumPopulation][$iGen]	;Массив нового поколения
	Dim $aPopInGenerate	= 0						;Популяция нового поколения
	For $i = 0 To UBound($aCombineArray)-1 Step 2
		;Сохраняем геном родителей
		For $j = 0 To $iGen-1
			;Сохраняем различие генома (шаг)
			$aDiffGen[$j] = Round(($aCombineArray[$i][$j]-$aCombineArray[$i+1][$j])/5)
			If $aDiffGen[$j] = 0 Then	;Если предыдущий ген родителя не отличается от гена второго родителя
				$aDiffGen[$j] = Random(0, $iEndGen, 1)	;Будет мутация!!!111
			EndIf
			
			;ConsoleWrite(@TAB&'разница ('&$aCombineArray[$i][$j]&', '&$aCombineArray[$i+1][$j]&') генома '&@TAB&$aDiffGen[$j])
			;Создаем 4 новые особи
			For $k = 0 To 3
				$aEnclave[$k][$j] = $aCombineArray[$i][$j] - ($k+1)*$aDiffGen[$j]
			Next
			;ConsoleWrite(@TAB&' записали в новую особь '&$aEnclave[0][$j]&@CRLF)
		Next
		
		;Сохраняем особей из анклава в новое поколение
		$iGenerateIndex = $aPopInGenerate
		For $m = 0 To 3
			For $g = 0 To $iGen-1
				$aNewGenerate[$iGenerateIndex][$g] = $aEnclave[$m][$g]
			Next
			$iGenerateIndex += 1
		Next
		$aPopInGenerate += 4	;Сохраним значение популяции +4 ура ура ура
	Next
	
	Return $aNewGenerate
EndFunc
#endregion

#region КОД ПРОГРАММЫ
If $view Then StartView()
Dim $iFind			= 0
Dim $iTimer			= TimerInit()
Dim $iNumGenerate	= 0
;Генерируем первое поколение
$aPopulation	= FirstGenerate($iNumPopulation, $iGen, $iStartGen, $iEndGen)

Do
	;Проверка поколения на выживаемость
	$aSurvival = Fitness($aPopulation, $iNumPopulation, $iGen, $iCalcSentence, $iNeededResult)
	
	If IsInt($aSurvival) Then	;Если в результате вычисления пришло число - результат
		ConsoleWrite(Round(TimerDiff($iTimer)/1000, 4)&' - пришло число '&$aSurvival&'[')
		For $i=0 To $iGen-1
			ConsoleWrite($aPopulation[$aSurvival][$i]&'|')
		Next
		ConsoleWrite('] '&$iNumGenerate&@CRLF)
		$iFind = 1
		ExitLoop
	EndIf
	ConsoleWrite(Round(TimerDiff($iTimer)/1000, 4)&' - пришел массив '&$iNumGenerate&@CRLF)
	
	$aPopulation	= Selection($aSurvival, $aPopulation, $iNumPopulation, $iGen, $iEndGen)
	$iNumGenerate	+= 1
	Sleep(100)
Until $iFind = 1

If $view Then EndView()
#endregion

После того как отправил это сообщение он мне во втором поколении решение нашел, чудеса какие то не понятные :-X
 
Верх