otchet (1108529), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Это объясняется тем, что при большом количестве вершин очень мала вероятностьгенерации случайным образом графа-цикла. В дальнейшем при скрещивании и мутации может случиться так, что все графы в популяции как не былициклами, так и остались, то есть средний все популяции не изменился, тогдасрабатывает остановка алгоритма.

Вероятность этого растет с увеличениемчисла вершин в графе. Данная проблема решается, например, увеличениемчисла особой до 50, но тогда возрастает время работы алгоритма.10ЗаключениеРеализованная версия генетического алгоритма решает поставленную задачу с высокой точностью. Также алгоритм выигрывает у решения переборомпо времени. Это достигается за счет значительного сокращения рассматриваемых потенциальных ответов. Увеличение числа вершин в графе несильновлияет на время работы генетического алгоритма, в то время как у переборного оно растет по экспоненте. Так как задача сельского почтальона (как ипохожая задача коммивояжера) принадлежит классу N P , то можно считать,что генетический алгоритм успешно с ней справился.11Приложение. КодпрограммыЛистинг 5.1: Генерация тестов#l a n g scheme/base( define ( gen - v e r t e x - name n )( s t r i n g ->symbol ( s t r i n g - append "v" ( number ->s t r i n g n ) ) ) )( define ( w e i g h t )( random 1 0 ) )( define f o l d e r " t e s t s / " )( define ( i n c x )(+ x 1 ) )( define ( push l s t elem )( if ( not ( member elem l s t ) ) ( c o n s elem l s t ) l s t ) )( define ( a l l - v e r t e x graph )( define ( h e l p e r graph r e s u l t )( if ( n u l l ? graph ) r e s u l t( h e l p e r ( c d r graph ) ( push ( push r e s u l t ( c a a r graph ) ) ( c a d a r graph ) ) ) ) )( h e l p e r graph ' ( ) ) )( define ( v e r t e x - n e i g h b o r s v e r t e x graph )( define ( h e l p e r edge )( cond ( ( and ( e q u a l ? ( c a r edge ) v e r t e x ) ( not ( e q u a l ? ( c a d r edge ) v e r t e x ) ) )( c o n s ( c a d r edge ) ( caddr edge ) ) )( ( and ( e q u a l ? ( c a d r edge ) v e r t e x ) ( not ( e q u a l ? ( c a r edge ) v e r t e x ) ) )( c o n s ( c a r edge ) ( caddr edge ) ) )( else ' ( ) ) ) )( if ( not ( member v e r t e x ( a l l - v e r t e x graph ) ) ) ' ( )( f i l t e r ( lambda ( x ) ( not ( n u l l ? x ) ) ) ( map h e l p e r graph ) ) ) )( define ( s o l v e r graph c o n t r o l - w e i g h t edge - l i s t )( define ( f i n d - h a m i l t o n i a n - c y c l e s t a r t v i s i t e d n e i g h b o r s w e i g h t c o n t r o l - e d g e s )( if ( n u l l ? n e i g h b o r s ) ' ( )( if ( and ( a s s o c s t a r t n e i g h b o r s ) ( eq ? ( l e n g t h ( a l l - v e r t e x graph ) )( length v i s i t e d ) ) )( let ( ( answer ( l i s t ( r e v e r s e ( c o n s s t a r t v i s i t e d ) ) (+ w e i g h t ( c d r( assoc start neighbors ) ) ) ) ) )( if ( and ( n u l l ? ( remove ( l i s t s t a r t ( c a r v i s i t e d ) )12( remove ( l i s t ( c a r v i s i t e d ) s t a r t )c o n t r o l - e d g e s ) ) ) ( not (> ( c a d r answer )c o n t r o l - w e i g h t ) ) ) answer ' ( ) ) )( if ( member ( c a a r n e i g h b o r s ) v i s i t e d )( f i n d - hamiltonian - c y c l e s t a r t v i s i t e d ( cdr neighbors ) weightcontrol - edges )( let ( ( ans1 ( f i n d - h a m i l t o n i a n - c y c l e s t a r t( cons ( caar neighbors )visited )( vertex - neighbors ( caarn e i g h b o r s ) graph )(+ w e i g h t ( c d a r n e i g h b o r s ) )( remove ( l i s t ( c a a rneighbors ) ( car v i s i t e d ) )( remove ( l i s t ( c a rv i s i t e d ) ( caarneighbors ) )c on t ro l - edges ) ) ) )( ans2 ( f i n d - h a m i l t o n i a n - c y c l e s t a r t v i s i t e d ( c d rneighbors ) weight c o n t r o l - edges ) ) )( cond ( ( n u l l ? ans1 ) ans2 )( ( n u l l ? ans2 ) ans1 )((< ( c a d r ans1 ) ( c a d r ans2 ) ) ans1 )( else ans2 ) ) ) ) ) ) )( if ( or ( n u l l ? graph ) (< c o n t r o l - w e i g h t 0 ) ) #f( let ( ( v - l i s t ( a l l - v e r t e x graph ) ) )( if ( n u l l ? ( c d r v - l i s t ) ) ( l i s t #t 0 v - l i s t )( let ( ( answer ( f i n d - h a m i l t o n i a n - c y c l e ( c a r v - l i s t ) ( l i s t ( c a rv - l i s t ) ) ( v e r t e x - n e i g h b o r s ( c a r v - l i s t ) graph ) 0 edge - l i s t ) ) )( if ( not ( n u l l ? answer ) )( l i s t #t ( c a d r answer ) ( c a r answer ) ) #f ) ) ) ) ) )( define ( gen - t e s t - e d g e s num- o f - v e r t e x )( define ( h e l p e r i t e r s r e s u l t )( if (= i t e r s 0 ) r e s u l t( let* ( ( n1 ( i n c ( random num- o f - v e r t e x ) ) ) ( n2 ( i n c ( randomnum- o f - v e r t e x ) ) ) ( new ( l i s t ( gen - v e r t e x - name n1 ) ( gen - v e r t e x - namen2 ) ) ) )( if ( or (= n1 n2 ) ( member new r e s u l t ) ( member ( r e v e r s e new ) r e s u l t ) )( helper i t e r s result )( h e l p e r ( - i t e r s 1 ) ( c o n s new r e s u l t ) ) ) ) ) )( h e l p e r ( random (max (+ ( q u o t i e n t num- o f - v e r t e x 2 ) 1 ) 1 ) ) ' ( ) ) )( define ( gen - c y c l e n )( define ( h e l p e r n r e s u l t )( if (= n 1 ) r e s u l t( h e l p e r ( - n 1 ) ( c o n s ( l i s t ( gen - v e r t e x - name ( - n 1 ) ) ( gen - v e r t e x - namen) ( weight ) ) r e s u l t ) ) ) )( if (> n 2 )( h e l p e r n ( l i s t ( l i s t ( gen - v e r t e x - name n ) ( gen - v e r t e x - name 1 ) ( w e i g h t ) ) ) )'() ) )( define ( gen - s t a r n )( define ( h e l p e r n r e s u l t )( if (= n 1 ) r e s u l t13( h e l p e r ( - n 1 ) ( c o n s ( l i s t ( gen - v e r t e x - name 1 ) ( gen - v e r t e x - name n )( weight ) ) r e s u l t ) ) ) )( if (> n 3 )( helper n '() ) '() ) )( define ( gen - f u l l n )( define ( h e l p e r n r e s u l t )( if (= n 1 ) r e s u l t( h e l p e r ( - n 1 ) ( f o l d r c o n s r e s u l t ( map ( lambda ( x ) ( l i s t( gen - v e r t e x - name ( i n c x ) ) ( gen - v e r t e x - name n ) ( w e i g h t ) ) ) ( b u i l d - l i s t( - n 1) values ) ) ) ) ) )( cond ((= n 1 ) ( l i s t ( l i s t ( gen - v e r t e x - name 1 ) ( gen - v e r t e x - name 1 ) ( w e i g h t ) ) ) )((> n 0 ) ( h e l p e r n ' ( ) ) ) ) )( define ( gen - random v - count )( define ( push elem l i s t )( if ( and ( not ( e q u a l ? ( c a r elem ) ( c a d r elem ) ) )( not ( a s s o c ( c a d r elem ) ( v e r t e x - n e i g h b o r s ( c a r elem ) l i s t ) ) )( not ( a s s o c ( c a r elem ) ( v e r t e x - n e i g h b o r s ( c a d r elem ) l i s t ) ) ) )( c o n s elem l i s t )list ))( define ( add - s i n g l e graph )( define a l l ( a l l - v e r t e x graph ) )( f o l d r c o n s graph( map ( lambda ( x ) ( l i s t ( gen - v e r t e x - name x ) ( gen - v e r t e x - name x )( weight ) ) )( f i l t e r ( lambda ( x ) ( not ( member ( gen - v e r t e x - name x ) a l l ) ) )( b u i l d - l i s t v - count i n c ) ) ) ) )( define ( h e l p e r e - c v - c r e s u l t )( if (= e - c 0 )( if (= ( l e n g t h ( a l l - v e r t e x r e s u l t ) ) v - c ) r e s u l t ( add - s i n g l e r e s u l t ) )( h e l p e r ( - e - c 1 ) v - c ( push ( l i s t ( gen - v e r t e x - name ( i n c ( random v - c ) ) )( gen - v e r t e x - name ( i n c ( random v - c ) ) ) ( w e i g h t ) ) r e s u l t ) ) ) )( if (> v - count 0 )( h e l p e r ( / ( ∗ ( - v - count 1 ) v - count ) 2 ) v - count ' ( ) ) ' ( ) ) )( define ( gen - c y c l e - t e s t s count )( define num- o f - v e r t e x (+ count 2 ) )( define (summ- o f - c y c l e c y c l e )( f o l d l + 0 ( map caddr c y c l e ) ) )( let ( ( c y c l e ( gen - c y c l e num- o f - v e r t e x ) ) (w (+ ( ∗ num- o f - v e r t e x 5 ) ( random ( ∗num- o f - v e r t e x 1 0 ) ) ) ) )( c a l l - with - output - f i l e ( s t r i n g - append f o l d e r " c y c l e - t e s t - v" ( number ->s t r i n gnum- o f - v e r t e x ) " .

i n " )( lambda ( out )( begin( w r i t e l n c y c l e out )( w r i t e l n w out )( w r i t e l n ' ( ) out ) ) )#: e x i s t s ' t r u n c a t e )( c a l l - with - output - f i l e ( s t r i n g - append f o l d e r " c y c l e - t e s t - v" ( number ->s t r i n gnum- o f - v e r t e x ) " . out " )( lambda ( out )14( if (< w (summ- o f - c y c l e c y c l e ) )( w r i t e #f out )( begin( w r i t e l n #t out )( w r i t e l n (summ- o f - c y c l e c y c l e ) out )( w r i t e ( c o n s ( gen - v e r t e x - name 1 ) ( map c a d r c y c l e ) ) out ) ) ) )#: e x i s t s ' t r u n c a t e ) )( if (> count 1 )( gen - c y c l e - t e s t s ( - count 1 ) ) ' ( ) ) )( define ( gen - s t a r - t e s t s count )( define num- o f - v e r t e x (+ count 3 ) )( c a l l - with - output - f i l e ( s t r i n g - append f o l d e r " s t a r - t e s t - v" ( number ->s t r i n gnum- o f - v e r t e x ) " .

Характеристики

Список файлов лабораторной работы