Программа для подбора ячеек в параллельные группы по внутреннему сопротивлению

[AndyBig]

Написал программку для подбора аккумуляторных ячеек с разным внутренним сопротивлением в параллельные группы, так чтобы разброс общего внутреннего сопротивления между группами был минимальным. Программа написана на скорую руку так как я ее видел для себя По идее не требует никаких библиотек и фреймворков.
Буду рад отзывам и предложениям
Входные данные
Информация об имеющихся ячейках загоняется в программу из файла .csv (значения, разделенные запятой) - меню File->Open. Такой файл легко сохраняется из Excel, или даже пишется руками в Блокноте. В таком файле каждая строка - это информация об одной ячейке. В этой строке находятся два или три значения с разделителями между ними в виде запятой или точки с запятой. В системах, где десятичным разделителем является запятая, разделителем значений в .csv служит точка с запятой. Например:

Код Выделить Развернуть

1;24,07;3254
2;24,97;3263
3;20,22;3268
В системах с десятичным разделителем точкой значения в .csv разделяются запятой. Пример:

Код Выделить Развернуть

1,21.31,3363
2,21.18,3357
3,21.18,3299
Программа нормально понимает оба варианта.
Первой строкой могут идти заголовки полей, программа это поймет и не попытается использовать заголовки как значения:

Код Выделить Развернуть

№,Resistence,Capacity
1,21.31,3363
2,21.18,3357
3,21.18,3299
В файле .csv должны быть два или три значения в каждой строке. Первое значение - это всегда какой-то цифровой идентификатор ячейки, например ее порядковый номер. Второе значение - это ее внутреннее сопротивление. Если есть и третье значение, то оно считается емкостью ячейки. Емкость пока никак не участвует в расчетах, она служит лишь для информации - программа выведет итоговый результат для каждой группы и максимальный разброс между группами не только по сопротивлениям, но и по емкостям. Если третьего значения в строках .csv нет, значит емкость нигде не выводится. Единицы сопротивлений могут быть любыми - миллиомы, омы, килоомы - это не играет роли. Главное, чтобы они были одинаковыми для всех ячеек. То же самое и для емкостей. Единственный нюанс - все значения выводятся с точностью до 3-го знака после запятой. Так что если у вас в файле будут указаны значения типа 0.000341, то хоть они и будут нормально считаны и учтены в расчетах, в показанных итогах вы будете видеть только 0.000.
Ограничение по максимальному количеству загружаемых ячеек - не более 1000 штук.
Интерфейс
Программа состоит из одного окна:

1 - Меню.
2 - Текстовый лог событий и результатов.
3 - Количество параллельных ячеек в группе.
4 - Метод подбора ячеек в группы (подробности ниже).
5 - Флажок поиска заданного разброса сопротивлений между группами (подробности ниже).
6 - Заданный разброс сопротивлений между группами.
7 - Количество итераций подбора комбинаций ячеек в группы.
8 - Количество одновременно работающих потоков по подбору комбинаций.
9 - Кнопка начала перебора комбинаций.
10 - Кнопка очистки текстового лога.
11 - Кнопка ручного прерывания перебора.
Методы подбора ячеек в группы
Пока реализовано три метода:
S&T - перебор полностью случайных комбинаций в поиске оптимальной (Shake & Try). Этот метод показывает хороший результат при небольшом количестве ячеек - до 30-50 штук. Если ячеек больше 50, то этот метод практически не имеет смысла.
K-CR - подбор методом k-средних с рандомизацией исходного массива. Эффективен при среднем количестве ячеек - от 30 до 50-70.
K-C - подбор методом k-средних с упорядочиванием исходного массива. Дает мгновенный отличный результат при большом количестве ячеек - от 50 и больше.
Эффективность методов так же зависит от разброса сопротивлений ячеек и от количества ячеек в группе, но не так сильно как от общего количества ячеек. В любом случае при количестве ячеек до 60-80 штук имеет смысл попробовать все три метода и выбрать наилучший результат, если же ячеек больше 80, то первые два метода только займут время и почти гарантированно проиграют быстрому методу K-C.
Для первых двух методов требуется множество итераций перебора комбинаций для повышения шанса найти наиболее оптимальный результат. Максимальное количество итераций указывается в поле 7. Для ускорения процесса перебора процесс происходит одновременно в нескольких потоках, количество потоков задается в поле 8. Эффективное максимальное количество потоков зависит от системы и определяется загрузкой процессора. Если вы задали 20 потоков и загрузка процессора вышла на 100%, значит задавать большее количество потоков не имеет смысла.
Чем больше итераций будет задано тем выше шанс, что будет найдена наиболее оптимальная комбинация, но тем больше времени будет идти перебор. 1 итерация означает перебор 5000 комбинаций, из которых выбирается наиболее оптимальный вариант, таким образом 10'000 итераций будет означать 50'000'000 перебранных комбинаций.
Третий метод - KC - всегда выполняется за один проход в одном потоке, этот метод чисто вычислительный, без случайных комбинаций. При его выборе поля количества итераций и потоков становятся недоступными.
Галочка 5 - поиск заданного разброса между группами - означает, что перебор комбинаций будет остановлен как только будет найдена комбинация, при которой разброс между группами будет не больше заданного в поле 6 значения. Если такой комбинации не будет найдено, то перебор будет закончен после указанного в поле 7 количества итераций.
Работа программы
После запуска перебора программа будет выводить в лог все наиболее оптимальные комбинации, найденные на данный момент, расписывая их по группам и приводя общие результаты. После завершения перебора в лог еще раз выведется наиболее оптимальный из найденных результатов.
Полоса прогресса под логом показывает текущий прогресс итераций.
Пока что сохранения результатов нет ни в каком виде, но их можно просто скопировать из поля лога

Ссылка на программу: https://drive.google.com/file/d/1HQUCqYnPOB468PwubuvksAn8iLaSXvyW/view?usp=sharing
Это архив с одним исполняемым файлом, вирусов быть не должно, т.к. у меня стоит антивирус со свежими базами

[AndyBig]

Немного дописал программу до версии 1.1:
1. Все найденные комбинации сохраняются в файл лога accucels_log.txt , который создается в том же каталоге, откуда был открыт файл .csv со списком ячеек. При каждом запуске подбора этот файл перезаписывается заново.
2. Ячейки в группах в найденных комбинациях упорядочиваются по номерам, а сами группы упорядочиваются по общему сопротивлению.
3. Уменьшил холостой вывод в экранный лог в процессе подбора.
Прикладываю архив с программой.
cells_select_1.1.zip

[yurgen]

Буду рад отзывам и предложениям

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

[AndyBig]

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

Ну пока только так. По емкости пока можно руками выбрать из найденных комбинаций, где и разброс сопротивлений будет терпимым и разброс емкостей не слишком большим. Позже я хочу ввести весовой коэффициент для разброса емкостей, где 0 - это не обращать внимания на разброс емкостей, а 100 - подбирать только по емкостям.

[Telegnom]

Спасибо за программу! Очень мне упростила жизнь. Надеюсь будут еще версии.

Прикинул реально ли втупую перебрать все комбинации. Для сборки KS2P количество вариантов будет высчитываться по формуле (2K-1)!!. То есть для сборки 10S2P возможно всего 654,729,075 вариаций расстановки аккумуляторов по группам, для 13S2P - уже 7,905,853,580,625.
Для KSMP количество комбинаций - это произведение k-ых сумм первых n чисел натурального ряда, где 1SMP - первый член арифметической прогрессии вида a_n=a_n-1+M. Чтобы найти количество комбинаций, нужно перемножить все суммы членов прогрессии до K. Сумма первых чисел находится по известной формуле (n(n+1))/2. То есть, 4S3P - прогрессия 1 4 7 10, сумма первых членов 1 10 28 55, количество комбинаций 1*10*28*55=15,400. 10S3P, соответственно - 8,8888511 × 10*15. 4S4P - 1 5 9 13, 1*15*45*91 = 61,425 и так далее. 
Если я неправильно помню комбинаторику - поправьте.

[AndyBig]

Спасибо за программу! Очень мне упростила жизнь. Надеюсь будут еще версии.

Да, есть еще пара идей, но чисто сервисных, для большего удобства.

Прикинул реально ли втупую перебрать все комбинации. Для сборки KS2P количество вариантов будет высчитываться по формуле (2K-1)!!. То есть для сборки 10S2P возможно всего 654,729,075 вариаций расстановки аккумуляторов по группам, для 13S2P - уже 7,905,853,580,625.
Для KSMP количество комбинаций - это произведение k-ых сумм первых n чисел натурального ряда, где 1SMP - первый член арифметической прогрессии вида a_n=a_n-1+M. Чтобы найти количество комбинаций, нужно перемножить все суммы членов прогрессии до K. Сумма первых чисел находится по известной формуле (n(n+1))/2. То есть, 4S3P - прогрессия 1 4 7 10, сумма первых членов 1 10 28 55, количество комбинаций 1*10*28*55=15,400. 10S3P, соответственно - 8,8888511 × 10*15. 4S4P - 1 5 9 13, 1*15*45*91 = 61,425 и так далее. 
Если я неправильно помню комбинаторику - поправьте.

Формулы сейчас уже не помню, но у нас тут есть нюанс - нам нужно искать количество сочетаний, а не комбинаций, то есть порядок элементов внутри комбинаций не имеет значения. Например, для нас комбинации {1,2,3} и {3,2,1} одинаковы. Это уменьшает число перебираемых вариантов, например сочетаний 20 элементов по 2 для 10S2P - всего 190, сочетаний 26 элементов по 2 для 13S2P - 325, а вот тех же 26 элементов по 4 для 6S4P - уже 14950
Но в целом - да, с ростом общего числа перебираемых элементов и особенно количества элементов в группе - количество возможных вариантов резко растет. Плюс нужно составлять группы не просто по одной, а комплексно, из всех имеющихся элементов сразу, что тоже привносит сложности. Так что я отказался от перебора всех сочетаний подряд в пользу перебора случайных сочетаний для небольшого количества элементов и алгоритмического подбора для большого количества. Хотя может быть и зря отказался...

[Telegnom]

нам нужно искать количество сочетаний, а не комбинаций, то есть порядок элементов внутри комбинаций не имеет значения

Мы сначала из множества элементов создаем сочетания по формуле Ckn=n!/((n−k)!⋅k!). То есть для у нас есть 20 элементов, мы хотим их сложить группками по 2 в каждой - получится всего 190 вариаций группок, порядок элементов в группке при этом не учитывается (там, где учитывается, называется перестановкой) . Но на этом не всё - нужно выбрать такие группки, при которых разброс значения в них будет минимальным и использовались все элементы. И тут количество вариаций будет уже отличаться.
Два примера: 3S2P - 15 вариаций есть для раскладывания элементов по группкам 6 батарей - 12, 13, 14, 15, 16, 23, 24, 25, 26, 34, 35, 36, 45, 46, 56.
И количество вариантов сборки из это группы тоже будет 15 (формула (2K-1)!!). 12.34.56, 12.35.46, 12.36.45, 13.24.56, 13.25.46, 14.23.56, 15.23.46, 16.25.34 и так далее. Для первой позиции у нас есть 5 вариантов, для второй 3 и для третьей  - 1 оставшаяся.
Для 2S3P - 20 сочетаний, но только 10 вариантов сборок - 123.456, 124.356, 125.346, 126.345, 134.256, 135.246, 145.236, 146.235, 156.234.
Найти все возможные сочетания довольно просто, даже для монструозных батарей типа 13S6P это всего 256,851,595 вариантов сочетаний, пара минут счета. А вот вариантов расстановки будет >10^200
В принципе, количество вариантов можно уменьшить, отсекая сочетания с очень высоким и очень низким суммарным сопротивлением, но тут надо глубже в матан погружаться.
[/quote]

Хотя может быть и зря отказался...

Если я правильно помню указанные выше формулы - то для небольших сборок реально всё перебрать, а для таких, где элементов больше 20 - уже, скорее всего нет, только если это делать не на суперкомпьютере.

[AndyBig]

Если я правильно помню указанные выше формулы - то для небольших сборок реально всё перебрать, а для таких, где элементов больше 20 - уже, скорее всего нет, только если это делать не на суперкомпьютере.

Тут не только в сборке вопрос, но и в исходном количестве ячеек. Например, тебе нужно составить 3S3P и у тебя есть 40 ячеек. Надо перебрать варианты из всех 40 ячеек, чтобы выделить из них 3 наиболее оптимальных сочетаний
Мне подсказали правильную формулу для определения общего количества всех уникальных вариантов разбивки ячеек на группы - (k*n)!/(n!*k!^n), где k - количество ячеек в группе, n - количество групп при разбивке. Например, перебрать варианты разбивки 8 ячеек на 4 группы по 2 - (2*4)!/(4!*2!^4)=105 вариантов, в каждом по 4 группы. А, например, перебрать варианты разбивки 20 ячеек на 10 групп по 2 - (2*10)!/(10!*2!^10)=654,729,075 вариантов, в каждом по 10 групп
То есть да, тупой перебор всех вариантов имеет смысл только при очень небольшом исходном количестве ячеек.

[Telegnom]

(k*n)!/(n!*k!^n),

Тут где-то ошибка.

8 ячеек на 4 группы (по 2) - (8*4)!/(4!*8!^4)=105 вариантов

105 вариантов для 4S2P правильно, а вот (8*4)!/(4!*8!^4) будет не 105.

[AndyBig]

Упс, конечно ошибся. k - количество ячеек в группе, n - количество групп. Так что количество вариантов для 4S2P (8 ячеек на 4 группы по 2) будет выглядеть как (2*4)!/(4!*2!^4)=105

[Зуев Виктор]

Народ  а чего програмка ругается "could not read values", какие такие данные она не смогла считать.
Прибор для измерения сопротивления еще едет так, что забил сопротивления с определителя ёмкости, для "попробовать".

[AndyBig]

Народ  а чего програмка ругается "could not read values", какие такие данные она не смогла считать.
Прибор для измерения сопротивления еще едет так, что забил сопротивления с определителя ёмкости, для "попробовать".

Измените расширение файла на .csv

[Зуев Виктор]

Измените расширение файла на .csv

Написано было что txt понимает. Но да в csv перестало матюкаться

[AndyBig]

Да, планировалась еще поддержка .txt с разделителями табуляцией, но руки пока так и не дошли

[ЕвгенийП]

Доброго дня у меня и csv файл не открывается.

[AndyBig]

Доброго дня у меня и csv файл не открывается.

Доброго!
Приложите файл, который не открывается, я гляну в чем там дело.

[ЕвгенийП]

Там 2 файла, busterno.csv не открылся, переделал по формату как у человека выше по сообщениям все открылось BUSTER.csv

[AndyBig]

Там 2 файла, busterno.csv не открылся, переделал по формату как у человека выше по сообщениям все открылось BUSTER.csv

У вас в busterno.csv почему-то все строчки целиком заключены в кавычки, поэтому программа и не понимала этот файл