2021年7月26日月曜日

TTS2

 このサイトは、WEBアプリと思っていたのですが、単にブラウザの音声合成機能を使っているだけのようです。ならばと、Windows10の音声合成も使ってみたのですが、ブラウザとはなぜか雲泥の差です。IBM Watsonも使ってみたのですが、WEBデモの質が何故か得られないので止めました。

2021年7月23日金曜日

制約付最短経路問題 離散解法か連続解法か

NSPの部分問題である制約付最短経路問題をできるだけ速く解くというのは、NSP最適化において重要です。 

二つのアプローチがあります。言い換えるとグラフ解法か、分岐限定法かということです。

どちらが速く求まるか?というのは、問題によります。要因として大きいのは、基数制約の個数です。基数制約Σx(i)<=y がないときは、グラフ解法の方が速く、基数制約の個数が多くなるに従って連続解法の方が速く求まる傾向にあります。グラフ解法では、基数制約の個数が増えると指数関数的に保持する状態メモリが増えてきます。そのためインスタンスによっては破綻する可能性があります。基数制約のない問題というのは考えにくいので、連続解法の方が汎用性があります。一方、基数制約が少なければ、グラフ解法速度は、連続解法を圧倒する場合もあるので、インスタンスにより解法を変えることが理想的です。

連続解法の問題は、分岐限定法の速度です。分岐限定法の前にヒューリスティクスでOpt解に近い解を得ることや、削除平面を使いますが、この分野は、商用MIPソルバの独壇場であり、商用MIPソルバには敵いません。また、絶対的な速度の他に、解が出るまでの時間が一定ではない、という問題もあります。グラフ解ならば、解が出て来るまでの時間はほぼ一定ですが、連続解法では、時間が読めないという問題もあります。

参考リンク

https://speakerdeck.com/umepon/mathematical-optimization-in-60-minutes

https://speakerdeck.com/umepon/branch-and-bound-algorithm-and-cutting-plane-algorithm-for-integer-programs

https://speakerdeck.com/umepon/approximation-algorithms-for-combinatorial-optimization-problems







2021年7月16日金曜日

基数制約とソフト許容エラー数との関係

 基数制約とは、数を数える制約のことで、一般に不等式になります。

Σxi <=Max

Σxi <=Min

単純な例で、30日中休みを8回だけ取る制約を考えます。この場合の探索空間(ありえる状態空間)は、どうなるでしょうか?

計算方法は、30C8-30C7です。30個から、8個取る組み合わせ、つまり

Σxi <=8から

Σxi <=7を引き算すれば、Σxi>=8 && Σxi<=8となります。

これをExcelで計算したのが上のテーブルです。組み合わせ数が、381万程度となります。
ソフト許容を1とした場合は、(8,8)→(9,7)に拡大されます。以下同様です。

ソフト許容を3とした場合は、探索空間が14倍に増えることを意味します。ソフトエラーまで含めれば、それだけ満たす可能性が増えることを意味しますが、同時に探索負荷が重くなる(時間がかかる)ことを意味します。

ちなみに、日数を31にしただけでも結構な違いがあります。これが月ごとの難易度の違いの原因です。

また、それ以上に休み数の違いがドラスティックな違いを生むことが分かります。

基数制約単体に限れば、上のように組み合わせ数は計算できますが、現実の制約は、制約郡であり複雑です。その総数を計算するのは容易ではありませんが、離散解法(グラフ解法)により個々のRoster(個々人)毎に正確に求めることは可能です。しかし、Rosters全体でみたときに、現実時間内に総数を求めることは、小さなインスタンスを除けば大変に難しいです。(出来ないと言った方がよいかもしれません)。

ソフト許容を無限に許せば、探索負荷が重くなるのは、想像できると思います。一方で、全てをハード制約にすれば、簡単に解のない事態になってしまいます。適度なソフト制約化が、Reasonableな時間で解を得る鍵となります。

2021年7月10日土曜日

日曜の準夜勤務が3週連続で入らないように設定をしたい

 1)制約の実装


曜日タイプで”U日”を定義しています。3回連続は、ハード制約として記述しています。

参考までに、2回連続をソフト制約として記述しています。

U日は、上図で、の集合になります。各々3連続を禁止すればよいことになります。
尚、上記例の場合 準=準a OR 準b となっています。


2)U日の実装

カレンダ上の"日"そのままですが、User用の日を意図しています。適宜追加変更してください。


3)3週連続を厳密に考えますと、前月2週間分のデータも必要となりますので、前月分を5日から14日に変更しています。(表示開始日)

以上で、

■3回連続日曜の準は禁止(ハード制約)

■2回は、なるべく避ける(ソフト制約)

の実装となります。なるべく避けるの優先度(他の制約との兼ね合い)は、ソフトレベルの重みで調整することができます。

2021年6月26日土曜日

カレンダ更新

 137Aで内蔵カレンダを更新しました。


Q.今年はオリンピック等の影響で、7月19日が祝日でなく、7/22、23がお休み、また、8月8日が祝日となり、それに伴い8月9日が振替休日となり、8/11は普通日となっております。設定済休みの定義を変更できる方法があればお教え頂けると幸いです。

Ans.

 ■設定済み休みは、内蔵カレンダで決まっているために、137Aで更新しました。137A以降では、上記の通りとなっており、そのままお使いになれます。

 ■上記以外で、職場の祝とカレンダ祝が一致していない場合もあろうかと思います。

 ●職場祝を追加する方法

 ●カレンダ祝を取り消す方法

 については、6月18日ブログ「祝を平日扱いにしたい」をご参照ください。






2021年6月19日土曜日

TTS調査

 (5) How to Use Text To Speech Software in 2021 for YouTube Videos | Full Guide - YouTube

昨日のような記事は、動画にしてナレーションを入れた方がはるかに分かりやすいと思いました。そこで、Text To Speechソフトを調査してみました。いくつか試して、IBM Watsonが良さそうに思いました。日本ではOndokuがありますが、英語版も考慮するとIBMがよいかなと思いました。


2021年6月18日金曜日

祝を平日扱いにしたい

 カレンダ上の祝を祝日ではなく、平日扱いにしたい

という場合の設定の仕方を説明します。

<考え方>

(1)制約で用いる祝は、カレンダ祝とは別に定義し、「特祝」とする

(2)祝でない日を祝日とする場合もあるので、それは、「祝1」として定義する

(3)祝は、通常は祝として作用させるが、上記のように平日扱いとしたい場合もあります。そういう日は、「強制平日扱い日」として定義します。

<祝1の実装>

まずは、簡単な方、祝1から実装してみましょう。

7月19日、下のようにカレンダ祝です。スケジュールナースⅢの設定済みの曜日は、予めカレンダで決まっており変えることが出来ません。


なので、別に定義する必要があります。この例では、特別の日の設定で、祝日1を7月22・23日に設定しています。


あとは、曜日集合で、「特祝」を定義します。

上で「特祝」の行をクリックすると、定義した曜日集合が右側にカレンダとして表示されます。確かに、7月19日以外に祝1の7月22・7月23日も「特祝」であることが確認できました。実装終了です。

<強制平日扱い日の実装>
しかし、今回の例では、カレンダ祝である7月19日は、祝ではなく平日扱いにしたいとします。その場合は、上の実装だと、7月19日は祝になってしまうので、追加変更することにします。そこで、まず以下のように7月19日祝を打ち消すための「強制平日扱い日」を定義します。

さらに、曜日集合で 「強制平日扱いではない」を定義します。右下カレンダを見ると7月19日以外の集合になっていますね。


これを祝とANDを取ってものをU祝として定義します。

U祝は、空集合となるので、右上カレンダでは、なにも選択されていない曜日集合になります。これで祝の打ち消しに成功しました。
U祝を祝の代わりとして「特祝」で置き換えれば、制約用の祝日定義「特祝」の完成です。希望通り7月22・23日のみを祝日として呼ぶことができます。

<特祝=祝1としないのはなぜ?>
そんな面倒な実装をしなくても、ユーザ用の祝1を祝の代わりに使えばよいのでは?という疑問が沸いてくるかもしれません。確かにそうなのですが、その場合、祝1を毎月定義しないといけなくなってしまうことに注意してください。定義し忘れて、カレンダ上の祝がうっかり平日扱いになってしまう可能性があります。当然解の結果として後で気づきますが、なんかおかしい、と悩む時間の方が勿体ないのです。(勤務表作成担当者が変わるたびに、悩むことになります。)

上の実装は、通常とは異なる必要な日だけを定義するだけでよいことに注意してください。通常は、カレンダ上の祝は、制約定義上の祝と同じく作用します。実装の中身は忘れてしまってよいのです。通常と異なる月は、今月は特別だな、ということが自明のはずですから、そのような意識のもとで定義することが出来ます。必要なときに必要なだけ定義する、というのがメンテナンス上好ましいのです。人間は忘却の生き物です。実装は少し面倒でも、後々、自然に楽に記述できる実装の方をお勧めします。一度上の実装をしておけば、7月に限らず、未来永劫、特別な月は、特別な日だけ定義すればよいのです。

<なんだか難しい>
確かに曜日集合の定義の仕方は難しいかもしれません。が、「かつ」「または」「でない」の3つしか演算子はありません。曜日集合の右側カレンダに各定義の曜日集合が黄色でマークされるので、マークカレンダを見ながらご自分が欲しい曜日集合を目指して記述していけばよいのです。

余談ですが、AND,OR,NOTは、ブール演算と呼ばれるもので、最新のスーパコンピュータも極論すれば、この3つしか使っていません。どんなに複雑な論理もこの3つの組み合わせで済むということを昔チューリングと言う人が証明しました。