Чемпионат Алгоритмов Оптимизации. - страница 117

 
Первое обращение к фф должно состоять иэ массива сформированного штатным ГСЧ МТ с равномерным распределением? Свой ГСЧ с нормальным распределением использовать нельзя? Пусть так я не настаиваю. Насчет критериев оценки. Вы предлагаете считать машинное время испольнение кода. Но, извините, это с другой оперы. Одно дело затачивать код под эффективный поиск экстремумов, а другое дело учитывать машинное время исплнения компонентов программы, которое к тому же зависит от состочния железа в данный момент. Адекватно бы было считать число обращений к фф. Но здесь я то же не настаиваю. Не хочется опять увязнуть в процедурных вопросах, да и для моего алгоритма это неважно. У меня сейчас один вопрос. Правило о том что кол. обращений к фф фиксировано и одинаково для всех актуально?
 

Yuri Evseenkov:
1. Первое обращение к фф должно состоять иэ массива сформированного штатным ГСЧ МТ с равномерным распределением? Свой ГСЧ с нормальным распределением использовать нельзя?

2.  Насчет критериев оценки. Вы предлагаете считать машинное время испольнение кода.

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

2. Уже определились, критериев оценки 2, точность и количество запусков ФФ. Но по ссылке я привел пример расчета, это было давно уже, там вместо кол-ва запусков стоит время. Поэтому я и уточнил в посте: точность и количество обращений к ФФ - это два критерия оценки, при этом точность в 3 раза предпочтительнее.

Согласно такому расчету мест в таблице мой алгоритм займет первое место по результатам Вашей задачки. Считаем: точность выше, значит критерий точность 3, а количество запусков ФФ больше, значит 0, итого 3+0=3, а Ваш алгоритм наберет 0+1=1, то есть меньше очков. Но это не значит что я победил в Вашей задаче, поскольку не соблюдены несколько условий. А если максимум ФФ заранее известен, то таблица рассчитается немного по другому, на первое "виртуальное" место ставится максимальное значение, а наши места рассчитываются уже исходя из этого (количество набранных балов получится другим).

 
Yuri Evseenkov:
Правило о том что кол. обращений к фф фиксировано и одинаково для всех актуально?

Нет, такого правила не было никогда. Есть только максимально допустимое. Чем меньше обращений - тем лучше, это второй по важности критерий после точности.

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

 
Alexander Laur:

Короче, бред, а не Чемпионат.

Критерии выявления победителя выдумываются на ходу.

Через 15 страниц еще нужно будет ввести параметр для оценки победителя.

Все с наскока, не продуманно.

А реальность оказывается сложнее хотелок. :)

Это Ваша сегодняшняя "Мысль Дня"? Или "Мысль Года"?

Критерии утверждены ещё надцать страниц назад, а принцип расчета и формулы ещё раньше. Флудорастов очень много, это усложняет усвояемость материала зрителями - теперь и Ваша заслуга в этом есть, можете себя поздравить.

Меня спросили - я ответил. Если завтра спросят - снова отвечу. Но завтра придет Вася Череззаборперелезайко и снова глубокомысленно заметит "Чемпионат гомно, правила на ходу придумывают!"..........  

 
Alexander Laur:
Тогда ответьте на вопрос: Почему точность в 3 раза ценнее количества обращения к ФФ?!

Я так решил, организатор потому что. Есть и другие причины.

Вы писали когда нибудь свой алгоритм оптимизации? Представляете себе например, что такое найти среди 2E16 значений 1-о верное, и при этом использовать только 50 попыток? Это сложнее чем найти иголку среди миллиарда стогов сена. И это только если параметр один, а если 500? 1000? 1000000?

 
Alexander Laur:
Интересуют, именно, "другие" причины, то бишь аргументы в пользу числа 3, а не числа 10, например.
Эмпирическое соотношение. Я готов подождать 3 минуты и получить в 3 раза точнее результат, чем за одну минуту и во столько же результат хуже. Другие соотношения не практичны.
 
Alexander Laur:
И это Вы считаете аргументом достойным для определения победителя?

А Вы считаете что я так не считаю? - зря так считаете.

Ответьте на этот мой вопрос:

Andrey Dik:

Вы писали когда нибудь свой алгоритм оптимизации? Представляете себе например, что такое найти среди 2E16 значений 1-о верное, и при этом использовать только 50 попыток? Это сложнее чем найти иголку среди миллиарда стогов сена. И это только если параметр один, а если 500? 1000? 1000000? 

 
Alexander Laur:
Я ничего не считаю, я спрашиваю и жду ответа. Зачем мне заниматься догадками, когда можно спросит и получить ответ от первоисточника.

Так ответил же. Эмпирическое соотношение. Научно обоснованного ответа Вы нигде не найдете.

Я пытался найти зависимость точности решения от количества обращений при заданной вероятности попадания вместе с Математом, у нас не получилось. Возможно это как то связано с правилом 3х сигм, но не факт.  

 
Alexander Laur:

...вопрос в лоб: а должен ли участвовать в Чемпионате алгоритм, который не может найти экстремум пусть не точно, а с заданной погрешностью?

Вот сижу и размышляю... Ответить в лоб или нет. Решил - надо ответить!))

Зачем Вы спрашивали про значимость критерия "точность" превышающую "обращения" в 3 раза? Если есть критерий "точность", то надо полагать что у участников будет не 100%-я точность... Для этого и есть критерий "точность" что бы ранжировать по точности. Отсюда делаем вывод  - может!, но не обязан (не должен), потому что зачем кому то соревноваться, если у него алгоритм всегда выдает 100%-о точный ответ, и это одновременно означает, что за приемлемое кол-во обращений к ФФ, раз уж ответ от алгоритма однажды получен. Поэтому однозначно - не должен! - мало того, такой алгоритм надо спрятать и никому не показывать.  

 

А и да... Есть очень важный момент. Если алгоритм не "знает" где расположен абсолютный максимум, а он его не знает, иначе зачем его искать?, то и нет возможности сравнить, с какой точностью найден максимум внутри алгоритма. Это мы "снаружи" можем только судить о степени точности алгоритма проводя над ним эксперименты, но задать алгоритму параметр "искать с вот такой точностью!" мы не можем, по уже, надеюсь, понятным причинам.  

 
Alexander Laur:

Отвечу просто:

1. Если алгоритм НЕ МОЖЕТ найти экстремум с заданной точностью, то этому алгоритму не место на Чемпионате;

2. Учитывая пункт 1, в определении победителя участвуют только алгоритмы, которые НАЙДУТ экстремум с заданной точностью;

3. Никакого ранжирования по точности. Точность задается диапазоном;

4. Определение победителя по количеству обращений к ФФ.

На этом удаляюсь, у нас 2 часа ночи.

Понятно.

Но так нельзя.

Во первых: нет объективных причин задавать точность. для кого то 1% отклонение не понравится, а для кого то 20% будет за счастье. во многом зависит от типа задачи и типа алгоритма. Задать "проходную точность" на чемпионате будет означать - отсеять разные интересные алгоритмические решения.

Во вторых: точность зависит от обращений к ФФ и при чем нелинейно. Для разных типов алгоритмов зависимость будет разной и нельзя вот так просто сказать "этот алгоритм хороший, а это плохой", для этого и используются два критерия, что бы как можно белее объективно оценить алгоритмы. Был ещё третий критерий - время работы алгоритма (не ФФ), но он очень субъективный, использующие OCL алгоритмы на одних машинах будут летать, а на других тормозить, в итоге зрители желающие протестировать решения участников не смогут получить адекватного мнения об алгоритмах. Поэтому остались только два критерия: точность и обращения к ФФ.