Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 59

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Аналогично, при 6 соседях (рис. 1 б) имеется 7 градаций, а при 4 соседях (рис. 1 в) — 5 градаций, поэтому для хранения каждого из таких результа­тов потребуется 3 бита. Соответственно, для ЛП обработки потребуется прореживание А на три массива, с применением системы битовых масок

E1 = (001001001.001)2 ;

E2 = (010010010...010)2 ;

E3 = (100100100...100)2. (8)

Эффективность ЛП алгоритма снижается при этом только трёхкратно.

Прореживание системой масок (7) или (8) и со­ответствующее кратное снижение эффективности ЛП обработки снимается полностью с применени­ем стекового ЛП алгоритма.

4. Стековый локально-параллельный алгоритм

Сортировка материала, попавшего в к-й сегмент стека, реализуется «методом пузырька». Поясним работу ЛП стекового алгоритма на примере. Пусть имеются 8-битные числа

А1 = 18810 = 101111002,

А2 = 11310 = 011100012,

А3 = 23510 = 111010112,

А4 = 2510 = 000110012, (9)

случайным образом выбранные в интервале от 0 до 255. Нижний индекс обозначает основание систе­мы счисления представления числа. В двоичном представлении для наглядности лидирующие нули сохранены.

Интерпретируем двоичные позиции, как сег­менты в ЛП представлении. Таким образом, вы­ражения (9) означают, что имеется четыре 8-сег-ментных РгП. Размер каждого сегмента — 1 бит. Стеками являются столбцы сегментов. Имеется ЛП набор из 8 стеков. Работа данного ЛП набора сте­ков заключается в том, что после первоначального заполнения единичные сегменты «проваливают­ся» максимально вниз, а нулевые, соответственно, «всплывают» вверх согласно алгоритму сортиров­ки «методом пузырька», который применяется к РгП посегментно, одновременно (локально-параллельно) ко всем сегментам. С набором дан­ных (9) это выглядит следующим образом:

} —

— {

— {

10111100

 

10111100

01110001

 

01110001

11101011

} — {

00001001

00011001

 

11111011

10111100

} — {

00000000

00000001

 

10111101

01111001

 

01111001

11111011

 

11111011

00000000

 

00000000

10111101

} — {

00111001

01111001

 

11111101

11111011

 

11111011

00000000 00111001

 

— {

11111001 11111111

} —

(10)

} —

Выражение (10) изображает последовательную смену 7 состояний набора РгП (1). Первое состоя­ние соответствует исходному (1), последнее —ситу­ации с полностью отсортированными сегментны­ми стеками: все единицы максимально смещены вниз. Сортировка (ЛП работа стеков) организова­на за 6 шагов переходов между состояниями. Фи­гурные скобки и стрелки переходов показывают, какие именно из РгП сопоставляются на каждом следующем шаге алгоритма сортировки.

Рассмотренный процесс включает два вложен­ных цикла. Внешний цикл обеспечивает (n-1)-кратное (где n число РгП, в примере n = 4) по­вторение внутреннего цикла с сокращением его объёма от (n-1) (три первые смены состояний) до 1 (последняя смена состояний).

Первый (самый правый, соответствующий младшим разрядам чисел А1 А4) стек не претер­певал изменений, т.к. оказалось, что изначальная расстановка единиц в нём не требует сортировки. 4-е и 5-е состояния тождественны, поскольку в результате сопоставления РгП А3 и А4 оказалось, что в этом цикле не происходит вертикального перемещения единиц («всплывания пузырьков»). Показателен 3-й справа разряд. В нём тремя по­следовательными обменами единица спускается из РгП А1 в РгП А4.

Рассмотрим бинарную процедуру сопостав­ления, обозначенную на (10) значком «—». Про­цедура включает арифметические операции «—» и «+», а так же побитовые (поразрядные) логические операции «END» и «XOR». Входными данными являются А и B, выходными изменённые зна­чения А и B. В процедуре используются константа E0 = 11111.11 («ЛП единица») и промежуточная переменная M. Приведём описание процедуры в обозначениях, принятых в [7]:

Local_Parallel_Stack()

1 M <- A "END" ( B "XOR" E0 ) (11)

2 A <- A M

3 B <- B + M

В ходе выполнения в посегментном битовом представлении для всех четырёх возможных ком­бинаций входных данных происходит следующее. Исходное состояние:

А = ...1...1...0...0... ;

B = .1.0.1.0. .

Константа:

E0=.1.1.1.1. .

Промежуточные состояния:

B "XOR" E0 = .0.1.1.0. ;

M = А "END" ( B "XOR" E0 ) = ...0...1...0...0... .

Состояние после завершения процедуры:

А = ...1...0...0...0... ; B = ...1...1...1...0....

Как следует из представленного, в тех сегмент­ных стеках, в которых имеется комбинация (1, 0), происходит преобразование (1, 0) — (0, 1), то есть при наличии «свободного места» единица «прова­ливается» вниз по стеку. Остальные стековые ком­бинации остаются без изменения.

После завершения сортировки стеков (столбцов текущего набора РгП (10) ), имеется весь исходный материал для формирования результата — ново­го набора значений соответствующего фрагмента КА. Так, если рассматривать пример (10) как от­носящийся к работе БКА с четырьмя соседями (рис. 1 а), разность

(А2 А1) = (00111001)2 (00000000)2 = (00111001)2

будет соответствовать правилу наличия трёх «жи­вых» ячеек-соседей. В ней единицами отмечены те позиции (ячейки КА), которые «выжили» в новом поколении КА, поскольку в текущем поколении они были окружены тремя единичными соседями. Со­ответственно, нулями обозначены «не выжившие» ячейки, которые в текущем поколении были окру­жены меньшим либо большим числом соседей.

Аналогично, выглядит ситуация с другим чис­лом соседей (рис. 1 б, в) и более сложным набором правил. Так, в случае БКА с 8 соседями (рис. 1 в) и «выживанием» ячейки при 3 или 4 соседях (рис. 2) стек состоит из восьми РгП B1, B2,..., Bm,..., B8. Здесь, как и в (9), B8 основание стека, B1 его вершина. При упорядочении РгП аналогично представленному в (10), после прохождения сорти­ровки в стеках, значение «1» в некоторой позиции m-го РгП обозначает наличие у соответствующейячейки не менее (9 — т) «единичных» ячеек-соседей. Поэтому ситуация с 3 или 4 «соседями» отображается в виде «1» в B6 и B5, соответственно, при наличии «0» в B5 и B4, соответственно. Резуль­тирующее выражение данного комбинированного решающего правила — (B4 B6).

5. Обсуждение результатов

Работа БКА с применением предложенного стекового алгоритма смоделирована в варианте с 8 соседями (рис. 1 а) на 32-разрядном процессоре, на языке Python. Размер поля модели 32 х 32 ячей­ки. Моделированием подтверждена работоспособ­ность стекового алгоритма. В процессе разработки выявлены следующие особенности стекового ва­рианта построения КА.

Позитивной стороной ЛП стекового алгоритма КА является универсальность подхода примени­тельно к различным вариантам правил поведения КА. Универсальность проявляется в независимости от объёма и конфигурации окружения (соседства), а так же в простоте выбора порогового уровня или диапазона уровней при определении «выживаю­щих» ячеек. Этим обеспечивается простота смены значений для ключевых параметров модели (числа ячеек-соседей, конфигурации соседства и правил перехода разметки ячеек) при экспериментальном подборе при исследовании применительно к кон­кретной моделируемой предметной области.

Достоинством стекового варианта алгоритма КА является существенное (в 3 — 4 раза) сокраще­ние времени обработки по сравнению с рассмо­тренным (п. 3) альтернативным ЛП вариантом с прореживанием РгП.

Ограничением выполненного моделирования ЛП стекового варианта БКА является размер поля: строка поля целиком помещена в одно РгП. Для размещения более длинных строк требуется не­сколько РгП и дополнительные алгоритмические решения по состыковке их концов (младшего сег­мента РгП и старшего сегмента (,+ 1)-й РгП) для правильной обработки соседства ячеек.

В разработанном варианте стековый алгоритм детерминировано реализует два вложенных цик­ла. В результате, возможны, хотя и редки, случаи «холостого» прохождения цикла, типа отмеченно­го выше, продемонстрированного в примере (10) — тождественность 4-го и 5-го состояний. Сокра­щение количества переборов за счёт изъятия этих «холостых» прохождений цикла — проблематично. Введение соответствующих дополнительных про­верок только усложнит и замедлит алгоритм, по­скольку возможные проверки в совокупности бу­дут в лучшем случае соизмеримы по сложности и объёму кода с основной процедурой (11).

В связи со сказанным, последующими направ­лениями исследования могут явиться, в частности:

— модифицирование алгоритма на случай пред­ставления строки поля КА несколькими РгП;

— поиск оптимизационных алгоритмических решений, в частности по сокращению «холостых» циклов;

— распространение стекового алгоритма на бо­лее широкий класс КА (большее число состояний ячейки, конфигурации соседства, отличные от ил­люстрируемых рис. 1, многомерные и многослой­ные структуры с послойными функциями влия­ния).

Кроме того ретроспективно целесообразны обобщения КА совместно с принципом ЛП и сте­ковым подходом в реализации базового алгоритма:

— введение весовых коэффициентов для уров­ней (при задании уровня срабатывания в виде диа­пазона значений) и отдельных полей конфигура­ции окружения;

— интерпретация вводимых весовых коэффи­циентов как значений ФП;

— вероятностная интерпретация ФП.

Введение вероятностных представлений и эле­ментов нечёткости — позволяет существенно раз­нообразить поведение КА и искать их устойчивые долгоживущие состояния (в смысле выживаемости КА) помимо зависимости от конкретных правил поведения КА.

Применительно к приложениям типа модели­рования различных аспектов функционирования живой природы нечёткий и вероятностный КА подходы принципиально интересны тем, что ими вводится (учитывается, изначально задаётся) мера детерминированности (известности, измеримо­сти, наблюдаемости) в поведении моделируемой системы. Таким образом, не исключаются из рас­смотрения неизвестные влияющие факторы, всег­да присутствующие в моделируемой системе.

Выводы

Локально-параллельное представление инфор­мации обеспечивает повышенную эффективность работы программного обеспечения. Принципы локально-параллельной обработки применимы к клеточным автоматам и позволяют существенно увеличить размеры модели. Предложен и проде­монстрирован на тестовых примерах локально-параллельный стековый алгоритм бинарного клеточного автомата. Стековый подход в равной степени эффективен применении к различному числу и вариантом расположения ячеек-соседей; а также инвариантен по выбору порогового уровня или диапазона уровней для определения «выжи­вающих» ячеек.

Список литературы: 1. Бенаддия, Абдельлатиф. Перспек­тивы реализации келлюлярных авторматов на локально-параллельных алгоритмах [Текст] / Бенаддия Абдельлатиф // Материалы международной научно-практическойконференции студентов и аспирантов "Информаци­онные технологии в экономике и образовании". М.: Российский университет кооперации, 2008. — С. 45—48. 2. Михаль, О.Ф. Моделирование распределенных информационно-управляющих систем средствами локально-параллельных алгоритмов обработки нечет­кой информации [Текст] / О.Ф. Михаль // Проблемы бионики: Всеукр. межвед. науч.-техн. сборник. — 2001.

Вып. 54. — С. 28—34. 3. Михаль, О.Ф. Принципы орга­низации систем нечеткого регулирования на однородных локально-параллельных алгоритмах [Текст] / О.Ф. Ми­халь, О.Г. Руденко // Управляющие системы и машины. 2001. № 3. С. 3—10. 4. Тоффоли, Т. Машины клеточных автоматов [Текст] : Пер. с англ. / Т. Тоффоли, Н. Марголус.

М., «Мир» 1991. — 280 с. 5. Люггер, Д.Ф. Искусствен­ный интеллект: стратегии и методы решения сложных проблем [Текст] / Д.Ф. Люггер М.: Изд. дом «Вильямс», 2005. — 864 с. 6. Любищев, А.А. Дисперсионный анализ в биологии [Текст] / А.А. Любищев. М.: Изд-во Моск. ун-та, 1986. 200 с. 7. Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест М.: МЦНМО, 2001. — 960 с.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа